Submission #100887

#	Time	Username	Problem	Language	Result	Execution time	Memory
100887		TAISA_	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	1398 ms	23672 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++){
		scanf("%lld",&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]>0LL));
			chmin(s[i],INF);
		}
	}
	while(q--){
		ll t,l,r;scanf("%lld%lld%lld",&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;
		printf("%d\n",vl-vr+1);
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&d[i]);
   ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll t,l,r;scanf("%lld%lld%lld",&t,&l,&r);
            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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