oj.uz

Submission #902365

# Submission time Handle Problem Language Result Execution time Memory
902365 2024-01-10T10:10:49 Z UmairAhmadMirza Wall (IOI14_wall) C++17
100 / 100
 716 ms 99428 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
int const N=2e6+5;
int const inf=1e5;
int rise[4*N];
int down[4*N];
void up_to_date(int node,int l,int r){
	if(l+1==r)
		return;
	if(rise[node]>0){
		int h=rise[node];
		rise[node]=0;
		rise[node*2]=max(h,rise[node*2]);
		down[node*2]=max(down[node*2],rise[node*2]);
		rise[node*2+1]=max(h,rise[node*2+1]);
		down[node*2+1]=max(down[node*2+1],rise[node*2+1]);
	}
	if(down[node]<inf){
		int h=down[node];
		down[node]=inf;
		if(l+1<r){
			down[node*2]=min(h,down[node*2]);
			rise[node*2]=min(rise[node*2],down[node*2]);
			down[node*2+1]=min(h,down[node*2+1]);
			rise[node*2+1]=min(rise[node*2+1],down[node*2+1]);
		}
	}
}
void update(int node,int s,int e,int l,int r,int h,int t){
	if(e<=l || r<=s)
		return;
	// cout<<node<<' '<<s<<' '<<e-1<<endl;
	// cout<<rise[node]<<' '<<down[node]<<endl;
	up_to_date(node,s,e);
	if(l<=s && e<=r){
		if(t==1){
			rise[node]=max(h,rise[node]);
			down[node]=max(down[node],rise[node]);
		}
		else{
			down[node]=min(h,down[node]);
			rise[node]=min(rise[node],down[node]);
		}
		// cout<<"leave"<<endl;
		// cout<<rise[node]<<' '<<down[node]<<endl;
		// cout<<endl;
	}
	else{
		int mid=(s+e)/2;
		update(node*2,s,mid,l,r,h,t);
		update(node*2+1,mid,e,l,r,h,t);
	}
}
void printing(int node,int l,int r){
	// cout<<"**"<<endl;
	// cout<<l<<' '<<r-1<<endl;
	// cout<<rise[node]<<' '<<down[node]<<endl;
	if(l+1==r)
		return;
	int mid=(l+r)/2;
	printing(node*2,l,mid);
	printing(node*2+1,mid,r);
}
int query(int node,int s,int e,int p){
	up_to_date(node,s,e);
	if(s+1==e)
		return rise[node];
	int mid=(s+e)/2;
	if(p<mid)
		return query(node*2,s,mid,p);
	else
		return query(node*2+1,mid,e,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < 4*N; ++i){
		down[i]=inf;
		rise[i]=0;
	}
	for (int i = 0; i < k; ++i){
		// cout<<endl;
		update(1,0,n,left[i],right[i]+1,height[i],op[i]);
// 		printing(0,0,n);
	}
	for (int i = 0; i < n; ++i)
		finalHeight[i]=query(1,0,n,i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 62892 KB Output is correct
2 Correct 13 ms 63196 KB Output is correct
3 Correct 11 ms 62928 KB Output is correct
4 Correct 16 ms 63116 KB Output is correct
5 Correct 18 ms 63080 KB Output is correct
6 Correct 13 ms 63152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63080 KB Output is correct
2 Correct 121 ms 76576 KB Output is correct
3 Correct 147 ms 70068 KB Output is correct
4 Correct 378 ms 80992 KB Output is correct
5 Correct 232 ms 82288 KB Output is correct
6 Correct 209 ms 80560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63036 KB Output is correct
2 Correct 11 ms 63068 KB Output is correct
3 Correct 12 ms 63072 KB Output is correct
4 Correct 20 ms 63288 KB Output is correct
5 Correct 19 ms 63084 KB Output is correct
6 Correct 13 ms 63080 KB Output is correct
7 Correct 10 ms 62924 KB Output is correct
8 Correct 135 ms 76624 KB Output is correct
9 Correct 136 ms 70392 KB Output is correct
10 Correct 374 ms 81012 KB Output is correct
11 Correct 213 ms 82012 KB Output is correct
12 Correct 235 ms 80496 KB Output is correct
13 Correct 10 ms 62812 KB Output is correct
14 Correct 121 ms 76548 KB Output is correct
15 Correct 33 ms 64080 KB Output is correct
16 Correct 435 ms 81256 KB Output is correct
17 Correct 225 ms 80536 KB Output is correct
18 Correct 234 ms 80720 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62808 KB Output is correct
2 Correct 11 ms 63172 KB Output is correct
3 Correct 11 ms 63068 KB Output is correct
4 Correct 14 ms 63308 KB Output is correct
5 Correct 14 ms 63068 KB Output is correct
6 Correct 14 ms 63064 KB Output is correct
7 Correct 12 ms 63068 KB Output is correct
8 Correct 131 ms 76500 KB Output is correct
9 Correct 138 ms 70136 KB Output is correct
10 Correct 364 ms 80972 KB Output is correct
11 Correct 215 ms 82064 KB Output is correct
12 Correct 210 ms 80464 KB Output is correct
13 Correct 10 ms 63068 KB Output is correct
14 Correct 123 ms 76524 KB Output is correct
15 Correct 36 ms 64092 KB Output is correct
16 Correct 456 ms 81260 KB Output is correct
17 Correct 236 ms 80760 KB Output is correct
18 Correct 209 ms 80624 KB Output is correct
19 Correct 663 ms 99428 KB Output is correct
20 Correct 666 ms 96736 KB Output is correct
21 Correct 647 ms 99408 KB Output is correct
22 Correct 623 ms 96848 KB Output is correct
23 Correct 643 ms 96928 KB Output is correct
24 Correct 633 ms 96880 KB Output is correct
25 Correct 669 ms 96776 KB Output is correct
26 Correct 654 ms 99240 KB Output is correct
27 Correct 716 ms 99248 KB Output is correct
28 Correct 675 ms 96852 KB Output is correct
29 Correct 647 ms 96684 KB Output is correct
30 Correct 632 ms 96784 KB Output is correct