# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
180308 | Akashi | Worst Reporter 3 (JOI18_worst_reporter3) | C++14 | 709 ms | 25504 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;
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 (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... |