Submission #100885

#	Time	Username	Problem	Language	Result	Execution time	Memory
100885		TAISA_	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	2032 ms	10480 KiB

worst_reporter3

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll MOD=1000000007LL;
const ll INF=(1<<30);
const ll LINF=(1LL<<60);
template<typename T> void chmax(T &a,T b){a=max(a,b);}
template<typename T> void chmin(T &a,T b){a=min(a,b);} 
int main(){
	ll n,q;cin>>n>>q;
	vector<ll> d(n+10),s(n+10);
	for(int i=1;i<=n;i++)cin>>d[i];
	s[0]=1;
	s[1]=d[1];
	for(int i=2;i<=n;i++){
		if(s[i-1]>=INF){
			s[i]=INF;
		}else{
			s[i]=s[i-1]*((d[i]/s[i-1])+(d[i]%s[i-1]>0));
		}
	}
	while(q--){
		ll t,l,r;cin>>t>>l>>r;
		if((t/s[0])*s[0]<l||-n+(t/s[n])*s[n]>r){
			cout<<0<<endl;
			continue;
		}
		ll ok=n,ng=-1;
		while(ok-ng>1){
			ll mid=(ok+ng)/2;
			ll pos=-mid+(t/s[mid])*s[mid];
			if(pos<=r){
				ok=mid;
			}else{
				ng=mid;
			}
		}
		int vr=ok;
		ok=0,ng=n+1;
		while(ng-ok>1){
			ll mid=(ok+ng)/2;
			ll pos=-mid+(t/s[mid])*s[mid];
			if(pos>=l){
				ok=mid;
			}else{
				ng=mid;
			}
		}
		int vl=ok;
		cout<<vl-vr+1<<endl;
	}
}

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