Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <stack>
- using namespace std;
- stack<int> otwarte;
- int przeszkody[500001][3]; // 0-dol 1-gora 2-x
- int poz[500001][3]; // 0-roznica y-ów z poprz przeszkoda 1-y 2-liczba przeskokow
- int mini(int a, int b)
- {
- return a < b ? a : b;
- }
- int main()
- {
- //printf("%d\n", mini(5, 3));
- int i, n, x, a, miny = 2e9, limit, wynik = 0, k, pom;
- //printf("%d\n", (-4)%2);
- scanf("%d %d", &n, &x);
- for (i = 1; i <= n; i++)
- {
- scanf("%d %d %d", &a, &przeszkody[i][0], &przeszkody[i][1]);
- przeszkody[i][0]++;
- przeszkody[i][1]--;
- if (a % 2 == 0)
- {
- if (przeszkody[i][0] % 2 != 0)
- przeszkody[i][0]++;
- if (przeszkody[i][1] % 2 != 0)
- przeszkody[i][1]--;
- }
- else
- {
- if (przeszkody[i][0] % 2 == 0)
- przeszkody[i][0]++;
- if (przeszkody[i][1] % 2 == 0)
- przeszkody[i][1]--;
- }
- przeszkody[i][2] = a;
- }
- for (i = 1; i <= n; i++)
- {
- if (przeszkody[i][0] > przeszkody[i][1])
- {
- //przeszkoda to tylko jeden nieosiagalny punkt
- printf("NIE\n");
- wynik = -1;
- break;
- }
- if (poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2]) > przeszkody[i][1])
- {
- //nie mozemy spasc
- printf("NIE\n");
- wynik = -1;
- break;
- }
- else if (poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2]) >= przeszkody[i][0])
- {
- //pelny spadek swobodny
- przeszkody[i][0] = poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2]);
- poz[i][1] = przeszkody[i][0];
- otwarte.push(i);
- poz[i][0] = poz[i][1]-poz[i-1][1];
- poz[i][2] = (przeszkody[i][1]-poz[i][1])/2;
- }
- else
- {
- if (przeszkody[i][0]-poz[i-1][1] > przeszkody[i][2]-przeszkody[i-1][2])
- {
- //trzeba robic przeskok
- k = ((przeszkody[i][0]-poz[i-1][1])-(przeszkody[i][2]-przeszkody[i-1][2]))/2; //-l. przeskokow
- while(!otwarte.empty() && k > 0)
- {
- pom = otwarte.top();
- limit = mini(poz[pom][2], (poz[pom-1][1]+(przeszkody[pom][2]-przeszkody[pom-1][2])-poz[pom][1])/2);
- //TUTAJ NAPISZ PODNOSZENIE WYKRESU
- if (k <= limit)
- {
- wynik += k;
- poz[pom][1] += 2*k;
- poz[pom][0] += 2*k;
- poz[pom][2] -= k;
- if (poz[pom][0] == przeszkody[pom][2]-przeszkody[pom-1][2])
- {
- //ZAMYKAMY KRAWEDZ
- otwarte.pop();
- if (!otwarte.empty())
- {
- poz[otwarte.top()][2] = mini(poz[otwarte.top()][2], poz[pom][2]);
- }
- }
- k = 0;
- }
- else
- {
- if (limit == 0)
- break;
- wynik += limit;
- k -= limit;
- poz[pom][1] += 2*limit;
- poz[pom][0] += 2*limit;
- poz[pom][2] -= limit;
- if (poz[pom][0] == przeszkody[pom][2]-przeszkody[pom-1][2])
- {
- //ZAMYKAMY KRAWEDZ
- otwarte.pop();
- if (!otwarte.empty())
- {
- poz[otwarte.top()][2] = mini(poz[otwarte.top()][2], poz[pom][2]);
- }
- }
- }
- }
- if (k > 0)
- {
- printf("NIE\n");
- wynik = -1;
- break;
- }
- else
- {
- wynik += przeszkody[i][2]-przeszkody[i-1][2];
- poz[i][0] = przeszkody[i][2]-przeszkody[i-1][2];
- poz[i][1] = przeszkody[i][0];
- poz[i][2] = (przeszkody[i][1]-poz[i][1])/2;
- if (!otwarte.empty())
- {
- pom = otwarte.top();
- poz[pom][2] = mini(poz[pom][2], poz[i][2]);
- }
- }
- }
- else
- {
- //nie trzeba
- wynik += (przeszkody[i][0]-(poz[i-1][1]-(przeszkody[i][2]-przeszkody[i-1][2])))/2;
- poz[i][1] = przeszkody[i][0];
- poz[i][0] = poz[i][1]-poz[i-1][1];
- poz[i][2] = (przeszkody[i][1]-poz[i][1])/2;
- if (poz[i][0] != przeszkody[i][2]-przeszkody[i-1][2])
- {
- otwarte.push(i);
- }
- else
- {
- if (!otwarte.empty())
- {
- pom = otwarte.top();
- poz[pom][2] = mini(poz[pom][2], poz[i][2]);
- }
- }
- }
- }
- }
- if (wynik != -1)
- printf("%d\n", wynik);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement