Submission #73505

#	Time	Username	Problem	Language	Result	Execution time	Memory
73505		mraron	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	2056 ms	14080 KiB

worst_reporter3

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