Submission #911426

#	Time	Username	Problem	Language	Result	Execution time	Memory
911426		amirhoseinfar1385	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	435 ms	24732 KiB

worst_reporter3

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

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

int find(int t,int l){
	int 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(int i=1;i<=n;i++){
		cin>>d[i];
	}
	dp[0]=1;
	val[0]=1;
	for(int 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(int i=0;i<q;i++){
		int t,l,r;
		cin>>t>>l>>r;
		int resr=find(t,r+1),resl=find(t,l);
		int res=resl-resr;
		if(t>=l&&t<=r){
			res++;
		}
		cout<<res<<"\n";
	//	cout<<"hey: "<<l<<" "<<r<<" "<<resl<<" "<<resr<<"\n";
	}
	//for(int i=1;i<=n;i++){
	//	cout<<"wtf: "<<i<<" "<<dp[i]<<" "<<val[i]<<"\n";
	//}
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81