Submission #911427

#	Time	Username	Problem	Language	Result	Execution time	Memory
911427		amirhoseinfar1385	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	481 ms	33284 KiB

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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81