Submission #1078118

#TimeUsernameProblemLanguageResultExecution timeMemory
1078118horiaboeriuFountain (eJOI20_fountain)C++17
100 / 100
108 ms20308 KiB
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MAXL 18 #define MAXN 100000 #define INFINIT 2000000000 int poz[MAXL][MAXN + 1], sum[MAXL][MAXN + 1], lung[MAXN + 1], v[MAXN + 1], st[MAXN + 1]; int readInt() { int x; char ch; ch = fgetc(stdin); while (isspace(ch)) { ch = fgetc(stdin); } x = 0; while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = fgetc(stdin); } return x; } int main() { int n, q, i, j, p, vf, p2, x, s; //tin cu un rmq al i-lea la care va ajunge dupa ce cade apa in jos de p ori(puetre a lui 2) //si tin si suma capacitatilor si fac cautarea binaar de la aib n = readInt(); q = readInt(); lung[0] = INFINIT; vf = 0; for (i = 1; i <= n; i++) { lung[i] = readInt(); v[i] = readInt(); while (lung[i] > lung[st[vf]]) { poz[0][st[vf]] = i; sum[0][st[vf]] = v[i];//suma capacitatilor a primelor (1 << j) pe care va cadea apa incepand de la st[vf] vf--; } vf++; st[vf] = i; } j = p = 1; while (p <= n) { for (i = 1; i <= n; i++) { poz[j][i] = poz[j - 1][poz[j - 1][i]]; sum[j][i] = sum[j - 1][i] + sum[j - 1][poz[j - 1][i]]; } j++; p *= 2; } p2 = 1; while ((1 << p2) <= n) { p2++; } p2--; for (i = 0; i < q; i++) { j = readInt(); x = readInt(); if (v[j] >= x) { printf("%d\n", j); } else { s = v[j];//pe asta nu am adunat-o in rmq for (p = p2; p >= 0; p--) { if (poz[p][j] > 0 && s + sum[p][j] < x) { s += sum[p][j]; j = poz[p][j]; } } //acum in j este ultimul la care apa inca e mai multa decat poate tine //deci in urmatorul apa se va opri printf("%d\n", poz[0][j]); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...