oj.uz

Submission #100885

# Submission time Handle Problem Language Result Execution time Memory
100885 2019-03-15T02:44:28 Z TAISA_ Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 10480 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 10480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 10480 KB Time limit exceeded
2 Halted 0 ms 0 KB -