oj.uz

Submission #539342

# Submission time Handle Problem Language Result Execution time Memory
539342 2022-03-18T18:10:06 Z 1ne Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 522 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int64_t>extra;
void combine(vector<int64_t>tree1,vector<int64_t>tree2,int64_t node){
	/*for (auto x:tree1){
		cout<<x<<" ";
	}
	cout<<"     - > ";
	for (auto x:tree2){
		cout<<x<<" ";
	}
	cout<<'\n';
	*/
	extra[node] = max(extra[node*2],extra[node*2 + 1]);
	auto right = lower_bound(tree2.begin(),tree2.end(),tree1.back()) - tree2.begin();
	while(right>=0){
		if (tree2[right]>=tree1.back() || right>=(int)tree2.size()){
			--right;
		}
		else break;
	}
	if (right>=0){
		extra[node] = max(extra[node],tree1.back() + tree2[right]);
	}
	// if there is a element in right segment which is less than left maximum
}
void build(vector<vector<int64_t>>&tree,vector<int64_t>&arr,int64_t node,int64_t node_low,int64_t node_high){
    if (node_low==node_high){
        tree[node].push_back(arr[node_low]);
    }
    else {
        int64_t mid  =(node_low+node_high)>>1;
        build(tree,arr,node*2,node_low,mid);
        build(tree,arr,node*2 + 1,mid+1,node_high);
        combine(tree[2*node],tree[node*2 + 1],node);
        merge(tree[2*node].begin(),tree[2*node].end(),tree[2*node + 1].begin(),tree[2*node + 1].end(),back_inserter(tree[node]));    
    }  
}
int64_t curans = 0;
int64_t maxxy = 0;
void query(vector<vector<int64_t>>&tree,int64_t node,int64_t node_low,int64_t node_high,int64_t query_low,int64_t query_high){
    if (node_low>node_high||query_high<node_low||query_low>node_high)return ;
    if (query_low<=node_low&&query_high>=node_high){
    	curans = max(curans,extra[node]);
    	auto right = lower_bound(tree[node].begin(),tree[node].end(),maxxy) - tree[node].begin();
		while(right>=0){
			if (tree[node][right]>=maxxy || right>=(int)tree[node].size()){
				--right;
			}
			else break;
		}
		if (right>=0){
			curans = max(curans,maxxy + tree[node][right]);
		}
	    maxxy = max(maxxy,tree[node].back());
	    return ;
    }
    int64_t mid = (node_low+node_high)>>1;
   	query(tree,node*2,node_low,mid,query_low,query_high);
   	query(tree,node*2 + 1,mid+1,node_high,query_low,query_high);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int64_t n,m;cin>>n>>m;
vector<int64_t>arr(n);
for (int64_t i = 0;i<n;++i){
	cin>>arr[i];
}
vector<vector<int64_t>>tree(8*n);
extra.resize(8*n,0);
build(tree,arr,1,0,n-1);
for (int64_t i = 0;i<m;++i){
	int64_t l,r,k;cin>>l>>r>>k;
	--l,--r;
	curans = 0;
	maxxy = 0;
	query(tree,1,0,n-1,l,r);
	//cout<<curans<<" "<<maxxy<<'\n';
	if (curans>k){
		cout<<0<<'\n';
	}
	else cout<<1<<'\n';
}
return 0;}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 6 ms 2644 KB Output is correct
13 Correct 6 ms 2644 KB Output is correct
14 Correct 7 ms 2772 KB Output is correct
15 Correct 7 ms 2812 KB Output is correct
16 Correct 6 ms 2644 KB Output is correct
17 Correct 5 ms 2004 KB Output is correct
18 Correct 6 ms 2704 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 201 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 47288 KB Output is correct
2 Correct 202 ms 47836 KB Output is correct
3 Correct 232 ms 47840 KB Output is correct
4 Correct 243 ms 47844 KB Output is correct
5 Correct 208 ms 47840 KB Output is correct
6 Correct 146 ms 47740 KB Output is correct
7 Correct 146 ms 47768 KB Output is correct
8 Correct 164 ms 47816 KB Output is correct
9 Correct 39 ms 1228 KB Output is correct
10 Correct 198 ms 47804 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 6 ms 2644 KB Output is correct
13 Correct 6 ms 2644 KB Output is correct
14 Correct 7 ms 2772 KB Output is correct
15 Correct 7 ms 2812 KB Output is correct
16 Correct 6 ms 2644 KB Output is correct
17 Correct 5 ms 2004 KB Output is correct
18 Correct 6 ms 2704 KB Output is correct
19 Correct 519 ms 97212 KB Output is correct
20 Correct 522 ms 97152 KB Output is correct
21 Correct 407 ms 97160 KB Output is correct
22 Correct 448 ms 97208 KB Output is correct
23 Correct 416 ms 97152 KB Output is correct
24 Correct 338 ms 97128 KB Output is correct
25 Correct 344 ms 97196 KB Output is correct
26 Correct 426 ms 97140 KB Output is correct
27 Correct 483 ms 97248 KB Output is correct
28 Correct 454 ms 97188 KB Output is correct
29 Correct 495 ms 97184 KB Output is correct
30 Correct 459 ms 97312 KB Output is correct
31 Correct 454 ms 97252 KB Output is correct
32 Correct 461 ms 97164 KB Output is correct
33 Correct 512 ms 97456 KB Output is correct
34 Correct 319 ms 97160 KB Output is correct
35 Correct 317 ms 97124 KB Output is correct
36 Correct 315 ms 97304 KB Output is correct
37 Correct 333 ms 97256 KB Output is correct
38 Correct 339 ms 97236 KB Output is correct
39 Correct 460 ms 97072 KB Output is correct
40 Correct 257 ms 60044 KB Output is correct
41 Correct 380 ms 96604 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 6 ms 2644 KB Output is correct
13 Correct 6 ms 2644 KB Output is correct
14 Correct 7 ms 2772 KB Output is correct
15 Correct 7 ms 2812 KB Output is correct
16 Correct 6 ms 2644 KB Output is correct
17 Correct 5 ms 2004 KB Output is correct
18 Correct 6 ms 2704 KB Output is correct
19 Runtime error 201 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -