oj.uz

Submission #73515

# Submission time Handle Problem Language Result Execution time Memory
73515 2018-08-28T11:19:17 Z mraron Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 12332 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
vector<int> get(int ti, vector<int>& t, int& n) {
	vector<int> akt(n);
	for(int i=0;i<n;++i) {
		akt[i]=-i-1;
	}
	
	vector<int> ans;
	for(int i=0;i<ti;++i) {
		for(int j=0;j<n;++j) {
			if(j==0) {
				if(abs(i-akt[j])>=t[j]+1) {
					akt[j]=i-1;
				}
			}else {
				if(abs(akt[j-1]-akt[j])>=t[j]+1) {
					akt[j]=akt[j-1]-1;
				}
			}
		}
		
		if(i==ti-1) {
			for(int j=n-1;j>=0;--j) {
				ans.push_back(akt[j]);
			}
		}
		
	}
	
	return ans;
}*/
int main() {
	int n,q;
	cin>>n>>q;
	vector<int> t(n);
	for(int i=0;i<n;++i) {
		cin>>t[i];
	}
	
	vector<ll> tt(n), mennyi(n);
	tt[0]=t[0];
	mennyi[0]=t[0];
	for(int i=1;i<n;++i) {
		if(t[i]>t[i-1]) {
			tt[i]=tt[i-1]*((t[i]+mennyi[i-1]-1)/mennyi[i-1]);
			mennyi[i]=tt[i];
		}else {
			tt[i]=tt[i-1];
			mennyi[i]=mennyi[i-1];
		}
	}
	
	for(int i=1;i<=q;++i) {
		ll ti,a,b;
		cin>>ti>>a>>b;
		//ti=i;
/*		for(int j=n-1;j>=0;--j) {
			cerr<<(-j-1+mennyi[j]*(ti/tt[j]))<<" ";
		}cerr<<ti<<"\n";
		
		for(auto j:get(ti, t, n)) {
			cerr<<j<<" ";
		}cerr<<ti<<"\n";*/
		
		
		//continue ;
		ll legelso, legutolso;
		
		ll L=0, R=n; //legelső a range előtt
		while(L<R) {
			
			ll mid=(L+R)/2;
			ll pos;
			if(mid<n) {
				assert(mid>=0&&mid<n);
				pos=-mid-1+mennyi[mid]*(ti/tt[mid]);	
			}else pos=-1e9;
		//cerr<<L<<" "<<R<<" "<<mid<<"LR\n";
			//cerr<<mid<<" "<<pos<<"\n";
		//	cerr<<ti<<"time "<<mid<<" "<<pos<<"\n";
			if(pos<a) {
				R=mid;
			}else {
				L=mid+1;
			}
		}
		
	//	cerr<<L<<"!!\n";
		legelso=L;
		L=-1;R=n-1; //legelső a range után
		while(L<R) {
			ll mid=(L+R+1)/2;
			ll pos;
			if(mid==-1) {
				pos=1e9;
			}else {
				assert(mid>=0&&mid<n);
				pos=-mid-1+mennyi[mid]*(ti/tt[mid]);
			}
	//		cerr<<L<<" "<<R<<"\n";
			if(pos>b) {
				L=mid;
			}else {
				R=mid-1;
			}
		}
		
		//cerr<<L<<" "<<R<<"can we hit 1212 lieks?\n";
		legutolso=L;
		
		//cerr<<legutolso<<" "<<legelso<<"\n";
		assert(legelso>=legutolso);

		cout<<legelso-legutolso-1+(a<=ti&&ti<=b)<<"\n";
	}
	
	/*for(int i=0;i<300;++i) {
		for(auto j:get(i, t, n)) {
			cerr<<j<<" ";
		}cerr<<i<<"\n";
	}
	
	for(auto i:tt) {
		cerr<<i<<" ";
	}cerr<<"\n";
	
	for(auto i:mennyi) {
		cerr<<i<<" ";
	}cerr<<"\n";
	*/
	
	
	return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

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