# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
242207 | cheeheng | Worst Reporter 3 (JOI18_worst_reporter3) | C++17 | 734 ms | 11308 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |