oj.uz

답안 #73516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73516 2018-08-28T11:20:59 Z mraron Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 1359 ms 263168 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() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1234 ms 17016 KB Output is correct
2 Correct 1359 ms 32728 KB Output is correct
3 Correct 1235 ms 48160 KB Output is correct
4 Correct 1169 ms 63476 KB Output is correct
5 Correct 1172 ms 79104 KB Output is correct
6 Correct 1196 ms 94524 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 94524 KB Output is correct
2 Correct 3 ms 94524 KB Output is correct
3 Correct 3 ms 94524 KB Output is correct
4 Correct 3 ms 94524 KB Output is correct
5 Correct 4 ms 94524 KB Output is correct
6 Correct 3 ms 94524 KB Output is correct

Subtask #3
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1234 ms 17016 KB Output is correct
2 Correct 1359 ms 32728 KB Output is correct
3 Correct 1235 ms 48160 KB Output is correct
4 Correct 1169 ms 63476 KB Output is correct
5 Correct 1172 ms 79104 KB Output is correct
6 Correct 1196 ms 94524 KB Output is correct
7 Correct 4 ms 94524 KB Output is correct
8 Correct 3 ms 94524 KB Output is correct
9 Correct 3 ms 94524 KB Output is correct
10 Correct 3 ms 94524 KB Output is correct
11 Correct 4 ms 94524 KB Output is correct
12 Correct 3 ms 94524 KB Output is correct
13 Correct 622 ms 108696 KB Output is correct
14 Correct 708 ms 125100 KB Output is correct
15 Correct 604 ms 140520 KB Output is correct
16 Correct 635 ms 156284 KB Output is correct
17 Correct 921 ms 176280 KB Output is correct
18 Correct 997 ms 195040 KB Output is correct
19 Correct 1016 ms 213776 KB Output is correct
20 Correct 1010 ms 232336 KB Output is correct
21 Correct 974 ms 250936 KB Output is correct
22 Runtime error 966 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
23 Halted 0 ms 0 KB -