Submission #1035210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1035210	2024-07-26T06:47:31 Z	Alexabcde1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	791 ms	29264 KB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;
long long n,q,a[500005],sttime[500005],t,l,r,mid,ll,rr;
long long f(long long tt,long long k){
	return ((tt)/sttime[k])*sttime[k]-k;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>q;
	for (int i=1;i<=n;i++) cin>>a[i];
	sttime[1] = a[1];
	for (int i=2;i<=n;i++){
		sttime[i] = ((a[i]+sttime[i-1]-1)/sttime[i-1])*sttime[i-1];
	}
	while (q--){
		cin>>t>>l>>r;
		long long ans=0;
		
		long long ansl=1; long long ansr=n;
		if (f(t,1)<l) goto skip;
		if (r<f(t,n)) goto skip;		
		ll=1; rr=n;

		
		while (ll<=rr){
			mid=(ll+rr)/2;
			if (l<=f(t,mid)){
				ansl=max(ansl,mid);
				ll=mid+1;
			}
			else rr=mid-1;
		}
		
		ll=1; rr=n;
		while (ll<=rr){
			mid=(ll+rr)/2;
			if (f(t,mid)<=r){
				ansr=min(ansr,mid);
				rr=mid-1;
			}
			else ll=mid+1;
		}
		
		if (ansl>=ansr) ans=ansl-ansr+1;
		skip:;
		
		/*
		for (int i=1;i<=n;i++){
			if (l<=f(t,i)&&f(t,i)<=r) ans++;
		}
		*/
		if (l<=t && t<=r) ans++;
		
		cout<<ans<<endl;
	}
}
/*
6 1
11
36
28
80
98
66
190 171 210
*/

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	728 ms	26708 KB	Output is correct
2	Correct	720 ms	26704 KB	Output is correct
3	Correct	755 ms	26700 KB	Output is correct
4	Correct	719 ms	26596 KB	Output is correct
5	Correct	719 ms	26608 KB	Output is correct
6	Correct	725 ms	26584 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	728 ms	26708 KB	Output is correct
2	Correct	720 ms	26704 KB	Output is correct
3	Correct	755 ms	26700 KB	Output is correct
4	Correct	719 ms	26596 KB	Output is correct
5	Correct	719 ms	26608 KB	Output is correct
6	Correct	725 ms	26584 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	600 KB	Output is correct
13	Correct	611 ms	25076 KB	Output is correct
14	Correct	620 ms	25684 KB	Output is correct
15	Correct	616 ms	24384 KB	Output is correct
16	Correct	630 ms	24912 KB	Output is correct
17	Correct	728 ms	29028 KB	Output is correct
18	Correct	710 ms	29008 KB	Output is correct
19	Correct	636 ms	29148 KB	Output is correct
20	Correct	629 ms	29012 KB	Output is correct
21	Correct	656 ms	29264 KB	Output is correct
22	Correct	740 ms	29264 KB	Output is correct
23	Correct	786 ms	29012 KB	Output is correct
24	Correct	735 ms	29264 KB	Output is correct
25	Correct	791 ms	26448 KB	Output is correct
26	Correct	765 ms	26708 KB	Output is correct
27	Correct	716 ms	28760 KB	Output is correct
28	Correct	749 ms	29008 KB	Output is correct
29	Correct	730 ms	28496 KB	Output is correct
30	Correct	747 ms	28756 KB	Output is correct
31	Correct	784 ms	29008 KB	Output is correct
32	Correct	777 ms	25084 KB	Output is correct
33	Correct	1 ms	348 KB	Output is correct