Submission #911427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911427	2024-01-18T21:55:11 Z	amirhoseinfar1385	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	481 ms	33284 KB

worst_reporter3

#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
long long d[maxn],n,q,dp[maxn],val[maxn];

bool check(long long t,long long l,long long mid){
	long long ret=(t/dp[mid])*val[mid]-mid;
	//cout<<"wtf: "<<mid<<" "<<ret<<" "<<l<<"\n";
	return ret<l;
}

long long find(long long t,long long l){
	long long low=0,high=n+1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(check(t,l,mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	return high;
} 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(long long i=1;i<=n;i++){
		cin>>d[i];
	}
	dp[0]=1;
	val[0]=1;
	for(long long i=1;i<=n;i++){
		dp[i]=dp[i-1]*((d[i]+val[i-1]-1)/val[i-1]);
		val[i]=(d[i]+val[i-1]-1)/val[i-1];
		val[i]*=val[i-1];
	}
	for(long long i=0;i<q;i++){
		long long t,l,r;
		cin>>t>>l>>r;
		long long resr=find(t,r+1),resl=find(t,l);
		long long res=resl-resr;
		if(t>=l&&t<=r){
			res++;
		}
		cout<<res<<"\n";
	//	cout<<"hey: "<<l<<" "<<r<<" "<<resl<<" "<<resr<<"\n";
	}
	//for(long long i=1;i<=n;i++){
	//	cout<<"wtf: "<<i<<" "<<dp[i]<<" "<<val[i]<<"\n";
	//}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	467 ms	15080 KB	Output is correct
2	Correct	440 ms	15020 KB	Output is correct
3	Correct	441 ms	15144 KB	Output is correct
4	Correct	448 ms	15212 KB	Output is correct
5	Correct	447 ms	15184 KB	Output is correct
6	Correct	481 ms	14980 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	467 ms	15080 KB	Output is correct
2	Correct	440 ms	15020 KB	Output is correct
3	Correct	441 ms	15144 KB	Output is correct
4	Correct	448 ms	15212 KB	Output is correct
5	Correct	447 ms	15184 KB	Output is correct
6	Correct	481 ms	14980 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	2 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4696 KB	Output is correct
13	Correct	292 ms	24028 KB	Output is correct
14	Correct	313 ms	29988 KB	Output is correct
15	Correct	278 ms	28244 KB	Output is correct
16	Correct	304 ms	28988 KB	Output is correct
17	Correct	347 ms	33024 KB	Output is correct
18	Correct	358 ms	33160 KB	Output is correct
19	Correct	345 ms	33284 KB	Output is correct
20	Correct	364 ms	33052 KB	Output is correct
21	Correct	353 ms	33108 KB	Output is correct
22	Correct	350 ms	33108 KB	Output is correct
23	Correct	357 ms	33044 KB	Output is correct
24	Correct	347 ms	33228 KB	Output is correct
25	Correct	449 ms	30640 KB	Output is correct
26	Correct	454 ms	30672 KB	Output is correct
27	Correct	459 ms	32668 KB	Output is correct
28	Correct	367 ms	33112 KB	Output is correct
29	Correct	386 ms	32768 KB	Output is correct
30	Correct	403 ms	32656 KB	Output is correct
31	Correct	381 ms	32944 KB	Output is correct
32	Correct	380 ms	29256 KB	Output is correct
33	Correct	1 ms	4444 KB	Output is correct