#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int N, Q;
cin >> N >> Q;
vector<int> D(N + 1, 1);
for (int i = 1; i <= N; i++) {
cin >> D[i];
}
// Compute the array X, which means the i-th person will move X[i] units every X[i] seconds
vector<long long> X(N + 1, 1);
for (int i = 1; i <= N; i++) {
X[i] = ((D[i] + X[i - 1] - 1) / X[i - 1]) * X[i - 1];
}
auto Query = [&](int T, int L, int R) { // Count T - R - i <= T mod X[i] <= T - L - i
int res = N + 1;
{ // Count how many i where T mod X[i] < T - R - i holds, and decrease it from answer.
// T mod X[i] is monotonically increasing, so we can binary search for it.
int lo = -1, hi = N;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (T % X[mid] < T - R - mid) {
lo = mid;
} else {
hi = mid - 1;
}
}
res -= lo + 1; // there are lo+1 such elements which T mod X[i] < T - R - i holds. (i = [0, N])
}
{ // Count how many i where T mod X[i] > T - L - i holds, and decrease it from answer.
// T mod X[i] is monotonically increasing, so we can binary search for it.
int lo = 0, hi = N + 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (T % X[mid] > T - L - mid) {
hi = mid;
} else {
lo = mid + 1;
}
}
res -= (N - lo) + 1; // there are N - lo + 1 such elements which T mod X[i] > T - L - i holds. (i = [0, N])
}
return res;
};
for (int qi = 0; qi < Q; qi++) {
int T, L, R;
cin >> T >> L >> R;
cout << Query(T, L, R) << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
619 ms |
13120 KB |
Output is correct |
2 |
Correct |
641 ms |
13256 KB |
Output is correct |
3 |
Correct |
621 ms |
13176 KB |
Output is correct |
4 |
Correct |
616 ms |
13048 KB |
Output is correct |
5 |
Correct |
616 ms |
13048 KB |
Output is correct |
6 |
Correct |
607 ms |
13024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
619 ms |
13120 KB |
Output is correct |
2 |
Correct |
641 ms |
13256 KB |
Output is correct |
3 |
Correct |
621 ms |
13176 KB |
Output is correct |
4 |
Correct |
616 ms |
13048 KB |
Output is correct |
5 |
Correct |
616 ms |
13048 KB |
Output is correct |
6 |
Correct |
607 ms |
13024 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
416 ms |
23160 KB |
Output is correct |
14 |
Correct |
400 ms |
23800 KB |
Output is correct |
15 |
Correct |
406 ms |
22392 KB |
Output is correct |
16 |
Correct |
393 ms |
23032 KB |
Output is correct |
17 |
Correct |
516 ms |
27348 KB |
Output is correct |
18 |
Correct |
504 ms |
27256 KB |
Output is correct |
19 |
Correct |
502 ms |
27256 KB |
Output is correct |
20 |
Correct |
494 ms |
27256 KB |
Output is correct |
21 |
Correct |
495 ms |
27288 KB |
Output is correct |
22 |
Correct |
500 ms |
27256 KB |
Output is correct |
23 |
Correct |
510 ms |
27128 KB |
Output is correct |
24 |
Correct |
489 ms |
27256 KB |
Output is correct |
25 |
Correct |
627 ms |
24696 KB |
Output is correct |
26 |
Correct |
630 ms |
24824 KB |
Output is correct |
27 |
Correct |
533 ms |
26872 KB |
Output is correct |
28 |
Correct |
523 ms |
27128 KB |
Output is correct |
29 |
Correct |
547 ms |
26620 KB |
Output is correct |
30 |
Correct |
532 ms |
26776 KB |
Output is correct |
31 |
Correct |
540 ms |
27128 KB |
Output is correct |
32 |
Correct |
493 ms |
23416 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |