# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
180308 | 2020-01-08T20:14:06 Z | Akashi | Worst Reporter 3 (JOI18_worst_reporter3) | C++14 | 709 ms | 25504 KB |
#include <bits/stdc++.h> using namespace std; const int INF = 1e9 + 1e6; int n, q; int d[500005], ad[500005]; inline int get_pos(int t, int i){ int wh = t / d[i]; return wh * d[i] - ad[i]; } inline int count_kids(int t, int x){ int st = 1, dr = n; while(st <= dr){ int mij = (st + dr) / 2; if(get_pos(t, mij) <= x) st = mij + 1; else dr = mij - 1; } return dr; } int main() { scanf("%d%d", &n, &q); d[1] = 1; ++n; ad[1] = 0; for(int i = 2; i <= n ; ++i){ scanf("%d", &d[i]); ad[i] = i - 1; int k = d[i] / d[i - 1]; if(d[i] % d[i - 1]) ++k; if(1LL * d[i - 1] * k >= INF) d[i] = INF; else d[i] = d[i - 1] * k; } for(int i = 1; i <= n / 2 ; ++i) swap(d[i], d[n - i + 1]), swap(ad[i], ad[n - i + 1]); int t, l, r; while(q--){ scanf("%d%d%d", &t, &l, &r); if(l > t) {printf("0\n"); continue ;} r = min(r, t); int nr = count_kids(t, r) - count_kids(t, l - 1); printf("%d\n", nr); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 687 ms | 22808 KB | Output is correct |
2 | Correct | 690 ms | 22864 KB | Output is correct |
3 | Correct | 690 ms | 22752 KB | Output is correct |
4 | Correct | 682 ms | 22776 KB | Output is correct |
5 | Correct | 686 ms | 22968 KB | Output is correct |
6 | Correct | 686 ms | 22924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 380 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 687 ms | 22808 KB | Output is correct |
2 | Correct | 690 ms | 22864 KB | Output is correct |
3 | Correct | 690 ms | 22752 KB | Output is correct |
4 | Correct | 682 ms | 22776 KB | Output is correct |
5 | Correct | 686 ms | 22968 KB | Output is correct |
6 | Correct | 686 ms | 22924 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 3 ms | 380 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 3 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 452 ms | 21468 KB | Output is correct |
14 | Correct | 458 ms | 21808 KB | Output is correct |
15 | Correct | 435 ms | 20728 KB | Output is correct |
16 | Correct | 453 ms | 21112 KB | Output is correct |
17 | Correct | 584 ms | 25464 KB | Output is correct |
18 | Correct | 585 ms | 25336 KB | Output is correct |
19 | Correct | 579 ms | 25416 KB | Output is correct |
20 | Correct | 582 ms | 25336 KB | Output is correct |
21 | Correct | 586 ms | 25504 KB | Output is correct |
22 | Correct | 591 ms | 25460 KB | Output is correct |
23 | Correct | 605 ms | 25268 KB | Output is correct |
24 | Correct | 586 ms | 25332 KB | Output is correct |
25 | Correct | 709 ms | 22720 KB | Output is correct |
26 | Correct | 705 ms | 22940 KB | Output is correct |
27 | Correct | 622 ms | 24896 KB | Output is correct |
28 | Correct | 613 ms | 25172 KB | Output is correct |
29 | Correct | 616 ms | 24696 KB | Output is correct |
30 | Correct | 645 ms | 24824 KB | Output is correct |
31 | Correct | 621 ms | 25284 KB | Output is correct |
32 | Correct | 541 ms | 21368 KB | Output is correct |
33 | Correct | 2 ms | 376 KB | Output is correct |