#include <bits/stdc++.h>
using namespace std;
int arr[500005];
int period[500005];
struct group{ int period, L, R; };
vector<group> G;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
for(int i = 1;i <= n;i++) cin >> arr[i];
period[0] = 1;
for(int i = 1;i <= n;i++){
int times = arr[i] / period[i-1];
if(arr[i] % period[i-1] != 0) times++;
period[i] = times * period[i-1];
}
int curR = 0;
for(int i = 0;i <= n;i++){
if(i == n || period[i] != period[i+1]){
G.push_back({period[i], -i, -curR});
curR = i+1;
}
}
while(q--){
int t, l, r; cin >> t >> l >> r;
int ans = 0;
for(group g : G){
int move = t / g.period;
int L = g.L + move * g.period;
int R = g.R + move * g.period;
///l, r are the query range. L, R are the range of people
ans += max(0,min({r-l, R-L, R-l, r-L})+1); ///overlap of the 2 ranges
}
cout << ans << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
308 ms |
22880 KB |
Output is correct |
2 |
Correct |
296 ms |
22776 KB |
Output is correct |
3 |
Correct |
300 ms |
22956 KB |
Output is correct |
4 |
Correct |
312 ms |
22648 KB |
Output is correct |
5 |
Correct |
316 ms |
22652 KB |
Output is correct |
6 |
Correct |
308 ms |
22776 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 |
512 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 |
308 ms |
22880 KB |
Output is correct |
2 |
Correct |
296 ms |
22776 KB |
Output is correct |
3 |
Correct |
300 ms |
22956 KB |
Output is correct |
4 |
Correct |
312 ms |
22648 KB |
Output is correct |
5 |
Correct |
316 ms |
22652 KB |
Output is correct |
6 |
Correct |
308 ms |
22776 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 |
512 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 |
328 ms |
21240 KB |
Output is correct |
14 |
Correct |
312 ms |
21752 KB |
Output is correct |
15 |
Correct |
298 ms |
20472 KB |
Output is correct |
16 |
Correct |
316 ms |
20984 KB |
Output is correct |
17 |
Correct |
424 ms |
25336 KB |
Output is correct |
18 |
Correct |
402 ms |
25312 KB |
Output is correct |
19 |
Correct |
416 ms |
25336 KB |
Output is correct |
20 |
Correct |
419 ms |
25360 KB |
Output is correct |
21 |
Correct |
409 ms |
25208 KB |
Output is correct |
22 |
Correct |
400 ms |
25464 KB |
Output is correct |
23 |
Correct |
405 ms |
25464 KB |
Output is correct |
24 |
Correct |
414 ms |
25336 KB |
Output is correct |
25 |
Correct |
304 ms |
22776 KB |
Output is correct |
26 |
Correct |
307 ms |
22908 KB |
Output is correct |
27 |
Correct |
402 ms |
24824 KB |
Output is correct |
28 |
Correct |
421 ms |
25208 KB |
Output is correct |
29 |
Correct |
417 ms |
24952 KB |
Output is correct |
30 |
Correct |
415 ms |
24824 KB |
Output is correct |
31 |
Correct |
419 ms |
25080 KB |
Output is correct |
32 |
Correct |
289 ms |
21368 KB |
Output is correct |
33 |
Correct |
4 ms |
384 KB |
Output is correct |