제출 #1035210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1035210		Alexabcde1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	791 ms	29264 KiB

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