# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
242207 | 2020-06-27T05:37:40 Z | cheeheng | Worst Reporter 3 (JOI18_worst_reporter3) | C++17 | 734 ms | 11308 KB |
#include <bits/stdc++.h> using namespace std; long long D[500005]; long long lag[500005]; bool boleh(int i, long long T, long long X){ long long pos = -i + T/lag[i]*lag[i]; //printf("boleh(%d, %lld, %lld): %lld\n", i, T, X, pos); return pos <= X; } int N, Q; int numAtMost(long long T, long long X){ int lo = 0; if(!boleh(N, T, X)){ return 0; } int hi = N; while(lo < hi){ int mid = (lo+hi)>>1; if(boleh(mid, T, X)){ hi = mid; }else{ lo = mid+1; } } return N-lo+1; } int main(){ scanf("%d%d", &N, &Q); for(int i = 1; i <= N; i ++){ scanf("%lld", &D[i]); } lag[0] = 1; for(int i = 1; i <= N; i ++){ lag[i] = (1+(D[i]-1)/lag[i-1]) * lag[i-1]; //printf("lag[%d]=%lld\n", i, lag[i]); } while(Q --){ long long T, L, R; scanf("%lld%lld%lld", &T, &L, &R); for(int i = 0; i <= N; i++){ boleh(i, T, 1); } //printf("next part\n"); int temp1 = numAtMost(T, L-1); int temp2 = numAtMost(T, R); //printf("%d %d\n", temp1, temp2); printf("%d\n", temp2-temp1); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 727 ms | 11220 KB | Output is correct |
2 | Correct | 707 ms | 11128 KB | Output is correct |
3 | Correct | 706 ms | 11144 KB | Output is correct |
4 | Correct | 734 ms | 11308 KB | Output is correct |
5 | Correct | 708 ms | 11128 KB | Output is correct |
6 | Correct | 718 ms | 11284 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 6 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 6 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 727 ms | 11220 KB | Output is correct |
2 | Correct | 707 ms | 11128 KB | Output is correct |
3 | Correct | 706 ms | 11144 KB | Output is correct |
4 | Correct | 734 ms | 11308 KB | Output is correct |
5 | Correct | 708 ms | 11128 KB | Output is correct |
6 | Correct | 718 ms | 11284 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 6 ms | 384 KB | Output is correct |
9 | Correct | 5 ms | 384 KB | Output is correct |
10 | Correct | 6 ms | 384 KB | Output is correct |
11 | Correct | 5 ms | 384 KB | Output is correct |
12 | Correct | 6 ms | 384 KB | Output is correct |
13 | Correct | 498 ms | 9220 KB | Output is correct |
14 | Correct | 484 ms | 9116 KB | Output is correct |
15 | Correct | 472 ms | 9208 KB | Output is correct |
16 | Correct | 490 ms | 9260 KB | Output is correct |
17 | Correct | 588 ms | 10656 KB | Output is correct |
18 | Correct | 588 ms | 10644 KB | Output is correct |
19 | Correct | 582 ms | 10588 KB | Output is correct |
20 | Correct | 581 ms | 10664 KB | Output is correct |
21 | Correct | 602 ms | 10612 KB | Output is correct |
22 | Correct | 598 ms | 10688 KB | Output is correct |
23 | Correct | 569 ms | 10616 KB | Output is correct |
24 | Correct | 582 ms | 10624 KB | Output is correct |
25 | Correct | 700 ms | 11160 KB | Output is correct |
26 | Correct | 711 ms | 11208 KB | Output is correct |
27 | Correct | 613 ms | 11132 KB | Output is correct |
28 | Correct | 617 ms | 11128 KB | Output is correct |
29 | Correct | 610 ms | 11000 KB | Output is correct |
30 | Correct | 616 ms | 11128 KB | Output is correct |
31 | Correct | 601 ms | 11000 KB | Output is correct |
32 | Correct | 565 ms | 10744 KB | Output is correct |
33 | Correct | 4 ms | 384 KB | Output is correct |