oj.uz

Submission #172624

# Submission time Handle Problem Language Result Execution time Memory
172624 2020-01-02T08:29:14 Z LinusTorvaldsFan Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 50088 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn=1000000+7;

int w[maxn];

const int K=400;

int block_answer[maxn];
int block_max[maxn];

const int Q=1<<18;
vector<int> tree[2*Q];

void build(int n) {
	for(int i=Q;i<Q+n;i++){
		tree[i].push_back(w[i-Q]);
	}
	for(int i=Q-1;i>0;i--){
		std::merge(tree[2*i].begin(),tree[2*i].end(),tree[2*i+1].begin(),tree[2*i+1].end(),std::back_inserter(tree[i]));
	}
}

int get(int l, int r, int x) {
	int ans=-1;
	//cout<<"::"<<l<<" "<<r<<endl;
	for(l+=Q,r+=Q;l<r;l>>=1,r>>=1){
		if(l&1) {
			auto t=lower_bound(tree[l].begin(),tree[l].end(),x);
			//cout<<tree[l].size()<<endl;
			if(t!=tree[l].begin()){
				t--;
				ans=max(ans,*t);
			}
			l++;
		}
		if(r&1) {
			r--;
			auto t=lower_bound(tree[r].begin(),tree[r].end(),x);
			if(t!=tree[r].begin()){
				t--;
				ans=max(ans,*t);
			}
		}
	}
	return ans;
}

int main() {
	// freopen("input.txt","r",stdin);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>w[i];
	
	for(int i=0;i+K-1<n;i+=K){
		int block=i/K;
		block_answer[block]=-1;
		for(int l=i;l<i+K;l++){
			for(int r=l+1;r<i+K;r++){
				if(w[l]>w[r]){
					block_answer[block]=max(block_answer[block],w[l]+w[r]);
				}
			}
		}
		
		for(int l=i;l<i+K;l++){
			block_max[block]=max(block_max[block],w[l]);
		}
		//cout<<block_answer[block]<<" ";
		//cout<<block_max[block]<<endl;
	}
	
	build(n);
	
	for(;m;m--){
		int l,r,k;
		cin>>l>>r>>k;
		l--; r--;
		int ans=-1;
		
		for(;l%K!=0 && l <= r;l++){
			int q=get(l+1,r+1,w[l]);
			//cout<<q<<endl;
			if(q!=-1) ans=max(ans,w[l]+q);		
		}
		
		
		for(;l+K-1<=r;l+=K){
			int block=l/K;
			ans=max(ans,block_answer[block]);
			int q=get(l+K,r+1,block_max[block]);
		//	cout<<":"<<q<<"\n";
			if(q!=-1) ans=max(ans,block_max[block]+q);
		}
		
		for(;l<=r;l++){
			int q=get(l+1,r+1,w[l]);
		//	cout<<q<<endl;
			if(q!=-1) ans=max(ans,w[l]+q);
		}
	//	cout<<ans<<endl;
		if(ans<=k){
			cout<<1<<'\n';
		} else {
			cout<<0<<'\n';
		}
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 18 ms 12664 KB Output is correct
3 Correct 23 ms 12664 KB Output is correct
4 Correct 19 ms 12664 KB Output is correct
5 Correct 20 ms 12664 KB Output is correct
6 Correct 40 ms 12792 KB Output is correct
7 Correct 39 ms 12792 KB Output is correct
8 Correct 32 ms 12668 KB Output is correct
9 Correct 30 ms 12664 KB Output is correct
10 Correct 27 ms 12660 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 18 ms 12664 KB Output is correct
3 Correct 23 ms 12664 KB Output is correct
4 Correct 19 ms 12664 KB Output is correct
5 Correct 20 ms 12664 KB Output is correct
6 Correct 40 ms 12792 KB Output is correct
7 Correct 39 ms 12792 KB Output is correct
8 Correct 32 ms 12668 KB Output is correct
9 Correct 30 ms 12664 KB Output is correct
10 Correct 27 ms 12660 KB Output is correct
11 Correct 275 ms 13032 KB Output is correct
12 Correct 371 ms 13384 KB Output is correct
13 Correct 424 ms 13400 KB Output is correct
14 Correct 684 ms 13540 KB Output is correct
15 Correct 685 ms 13656 KB Output is correct
16 Correct 284 ms 13652 KB Output is correct
17 Correct 151 ms 13440 KB Output is correct
18 Correct 228 ms 13336 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1435 ms 50088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 18 ms 12664 KB Output is correct
3 Correct 23 ms 12664 KB Output is correct
4 Correct 19 ms 12664 KB Output is correct
5 Correct 20 ms 12664 KB Output is correct
6 Correct 40 ms 12792 KB Output is correct
7 Correct 39 ms 12792 KB Output is correct
8 Correct 32 ms 12668 KB Output is correct
9 Correct 30 ms 12664 KB Output is correct
10 Correct 27 ms 12660 KB Output is correct
11 Correct 275 ms 13032 KB Output is correct
12 Correct 371 ms 13384 KB Output is correct
13 Correct 424 ms 13400 KB Output is correct
14 Correct 684 ms 13540 KB Output is correct
15 Correct 685 ms 13656 KB Output is correct
16 Correct 284 ms 13652 KB Output is correct
17 Correct 151 ms 13440 KB Output is correct
18 Correct 228 ms 13336 KB Output is correct
19 Execution timed out 3013 ms 40488 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 18 ms 12664 KB Output is correct
3 Correct 23 ms 12664 KB Output is correct
4 Correct 19 ms 12664 KB Output is correct
5 Correct 20 ms 12664 KB Output is correct
6 Correct 40 ms 12792 KB Output is correct
7 Correct 39 ms 12792 KB Output is correct
8 Correct 32 ms 12668 KB Output is correct
9 Correct 30 ms 12664 KB Output is correct
10 Correct 27 ms 12660 KB Output is correct
11 Correct 275 ms 13032 KB Output is correct
12 Correct 371 ms 13384 KB Output is correct
13 Correct 424 ms 13400 KB Output is correct
14 Correct 684 ms 13540 KB Output is correct
15 Correct 685 ms 13656 KB Output is correct
16 Correct 284 ms 13652 KB Output is correct
17 Correct 151 ms 13440 KB Output is correct
18 Correct 228 ms 13336 KB Output is correct
19 Runtime error 1435 ms 50088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -