# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
745312 | 2023-05-19T20:07:10 Z | rainboy | Fountain (eJOI20_fountain) | C | 346 ms | 20724 KB |
#include <stdio.h> #define N 100000 #define L 17 /* L = ceil(log2(N)) */ int main() { static int dd[N], cc[N], qu[N], pp[L + 1][N + 1], ss[L + 1][N + 1]; int n, q, cnt, i, l, s; scanf("%d%d", &n, &q); for (i = 0; i < n; i++) scanf("%d%d", &dd[i], &cc[i]); pp[0][n] = n, ss[0][n] = 0; cnt = 0; for (i = n - 1; i >= 0; i--) { while (cnt && dd[qu[cnt - 1]] <= dd[i]) cnt--; pp[0][i] = cnt == 0 ? n : qu[cnt - 1], ss[0][i] = cc[i]; qu[cnt++] = i; } for (l = 0; l < L; l++) for (i = 0; i <= n; i++) { pp[l + 1][i] = pp[l][pp[l][i]]; ss[l + 1][i] = ss[l][i] + ss[l][pp[l][i]]; } while (q--) { scanf("%d%d", &i, &s), i--; if (s > ss[L][i]) { printf("0\n"); continue; } for (l = L; l >= 0; l--) if (s > ss[l][i]) s -= ss[l][i], i = pp[l][i]; printf("%d\n", i + 1); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 2 ms | 596 KB | Output is correct |
5 | Correct | 2 ms | 596 KB | Output is correct |
6 | Correct | 2 ms | 644 KB | Output is correct |
7 | Correct | 2 ms | 644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 191 ms | 18524 KB | Output is correct |
2 | Correct | 247 ms | 17728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 2 ms | 596 KB | Output is correct |
5 | Correct | 2 ms | 596 KB | Output is correct |
6 | Correct | 2 ms | 644 KB | Output is correct |
7 | Correct | 2 ms | 644 KB | Output is correct |
8 | Correct | 191 ms | 18524 KB | Output is correct |
9 | Correct | 247 ms | 17728 KB | Output is correct |
10 | Correct | 2 ms | 564 KB | Output is correct |
11 | Correct | 94 ms | 10928 KB | Output is correct |
12 | Correct | 346 ms | 20724 KB | Output is correct |
13 | Correct | 239 ms | 20000 KB | Output is correct |
14 | Correct | 165 ms | 19264 KB | Output is correct |
15 | Correct | 135 ms | 19524 KB | Output is correct |