Submission #914708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914708	2024-01-22T14:58:51 Z	WongYiKai	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	464 ms	25428 KB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n,q;
	cin >> n >> q;
	ll cycle[n+1];
	cycle[0] = 1;
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		ll ii = i+1;
		if (temp <= cycle[i]) cycle[ii] = cycle[i];
		else cycle[ii] = temp+cycle[i]-(temp-1)%cycle[i]-1;
	}
	for (int i=0;i<q;i++){
		ll t,l,r;
		cin >> t >> l >> r;
		ll l2 = 0,r2 = n+1;
		while (l2<r2){
			ll m = l2+(r2-l2)/2;
			ll pos = -m + (t/cycle[m])*cycle[m];
			if (pos<=r) r2 = m;
			else l2 = m+1;
		}
		ll l3=0,r3=n+1;
		while (l3<r3){
			ll m = l3+(r3-l3)/2;
			ll pos = -m + (t/cycle[m])*cycle[m];
			if (pos>=l) l3=m+1;
			else r3=m;
		}
		cout << max(0LL,l3-l2) << "\n";
	}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	437 ms	23008 KB	Output is correct
2	Correct	450 ms	22636 KB	Output is correct
3	Correct	440 ms	22612 KB	Output is correct
4	Correct	454 ms	22700 KB	Output is correct
5	Correct	458 ms	22740 KB	Output is correct
6	Correct	445 ms	22668 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	437 ms	23008 KB	Output is correct
2	Correct	450 ms	22636 KB	Output is correct
3	Correct	440 ms	22612 KB	Output is correct
4	Correct	454 ms	22700 KB	Output is correct
5	Correct	458 ms	22740 KB	Output is correct
6	Correct	445 ms	22668 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	255 ms	21136 KB	Output is correct
14	Correct	268 ms	22140 KB	Output is correct
15	Correct	248 ms	20540 KB	Output is correct
16	Correct	269 ms	21132 KB	Output is correct
17	Correct	325 ms	25376 KB	Output is correct
18	Correct	352 ms	25424 KB	Output is correct
19	Correct	329 ms	25416 KB	Output is correct
20	Correct	339 ms	25172 KB	Output is correct
21	Correct	342 ms	25292 KB	Output is correct
22	Correct	328 ms	25428 KB	Output is correct
23	Correct	332 ms	25336 KB	Output is correct
24	Correct	325 ms	25424 KB	Output is correct
25	Correct	456 ms	22736 KB	Output is correct
26	Correct	464 ms	23132 KB	Output is correct
27	Correct	371 ms	24932 KB	Output is correct
28	Correct	400 ms	25080 KB	Output is correct
29	Correct	354 ms	24656 KB	Output is correct
30	Correct	359 ms	24776 KB	Output is correct
31	Correct	370 ms	25072 KB	Output is correct
32	Correct	347 ms	21332 KB	Output is correct
33	Correct	0 ms	344 KB	Output is correct