oj.uz

Submission #416957

# Submission time Handle Problem Language Result Execution time Memory
416957 2021-06-03T08:31:03 Z vanic Wall (IOI14_wall) C++14
100 / 100
 932 ms 102312 KB 
#include "wall.h"
#include <cmath>
#include <algorithm>

using namespace std;

const int maxn=2e6+5, Log=21, pot=(1<<Log);

int prop[pot*2][4];

void precompute(){
	for(int i=1; i<pot*2; i++){
		prop[i][1]=-1;
		prop[i][3]=-1;
	}
}
void dodaj(int x, int a, int b){
	if(prop[x][1]==-1){
		prop[x][0]=a;
		prop[x][1]=b;
	}
	else if(prop[x][3]==-1){
		if(b==prop[x][1]){
			if(b){
				prop[x][0]=max(prop[x][0], a);
			}
			else{
				prop[x][0]=min(prop[x][0], a);
			}
		}
		else{
			prop[x][2]=a;
			prop[x][3]=b;
		}
	}
	else{
		if(prop[x][3]==b){
			if(b){
				prop[x][2]=max(prop[x][2], a);
			}
			else{
				prop[x][2]=min(prop[x][2], a);
			}
		}
		else{
			if(b){
				if(a<=prop[x][2] && prop[x][0]<=prop[x][2]){
					prop[x][0]=max(prop[x][0], a);
				}
				else if(a>prop[x][2]){
					prop[x][0]=prop[x][2];
					prop[x][1]=prop[x][3];
					prop[x][2]=a;
					prop[x][3]=b;
				}
			}
			else{
				if(a>=prop[x][2] && prop[x][0]>=prop[x][2]){
					prop[x][0]=min(prop[x][0], a);
				}
				else if(a<prop[x][2]){
					prop[x][0]=prop[x][2];
					prop[x][1]=prop[x][3];
					prop[x][2]=a;
					prop[x][3]=b;
				}
			}
		}
	}
}
void propagate(int x){
	if(prop[x][1]==-1){
		return;
	}
	dodaj(x*2, prop[x][0], prop[x][1]);
	dodaj(x*2+1, prop[x][0], prop[x][1]);
	prop[x][1]=-1;
	if(prop[x][3]!=-1){
		dodaj(x*2, prop[x][2], prop[x][3]);
		dodaj(x*2+1, prop[x][2], prop[x][3]);
		prop[x][3]=-1;
	}
}
void update(int x, int L, int D, int l, int d, int a, int b){
	if(L>=l && D<=d){
		dodaj(x, a, b);
		return;
	}
	propagate(x);
	if((L+D)/2>=l){
		update(x*2, L, (L+D)/2, l, d, a, b);
	}
	if((L+D)/2+1<=d){
		update(x*2+1, (L+D)/2+1, D, l, d, a, b);
	}
}
void kraj(int x){
	if(x>=pot){
		return;
	}
	propagate(x);
	kraj(x*2);
	kraj(x*2+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	precompute();
	for(int i=0; i<k; i++){
		if(op[i]==2){
			op[i]=0;
		}
		update(1, 0, pot-1, left[i], right[i], height[i], op[i]);
	}
	kraj(1);
	int x;
	for(int i=0; i<n; i++){
		x=pot+i;
		if(prop[x][3]!=-1){
			if(prop[x][3]){
				finalHeight[i]=prop[x][2];
			}
			else{
				finalHeight[i]=min(prop[x][0], prop[x][2]);
			}
		}
		else if(prop[x][1]==1){
			finalHeight[i]=prop[x][0];
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65892 KB Output is correct
2 Correct 41 ms 65964 KB Output is correct
3 Correct 41 ms 65884 KB Output is correct
4 Correct 50 ms 66124 KB Output is correct
5 Correct 44 ms 66184 KB Output is correct
6 Correct 43 ms 66124 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 65820 KB Output is correct
2 Correct 302 ms 79488 KB Output is correct
3 Correct 263 ms 73036 KB Output is correct
4 Correct 654 ms 83920 KB Output is correct
5 Correct 335 ms 84896 KB Output is correct
6 Correct 329 ms 83412 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65820 KB Output is correct
2 Correct 41 ms 65988 KB Output is correct
3 Correct 41 ms 65884 KB Output is correct
4 Correct 46 ms 66144 KB Output is correct
5 Correct 44 ms 66164 KB Output is correct
6 Correct 44 ms 66140 KB Output is correct
7 Correct 38 ms 65868 KB Output is correct
8 Correct 304 ms 79584 KB Output is correct
9 Correct 254 ms 73028 KB Output is correct
10 Correct 645 ms 83864 KB Output is correct
11 Correct 335 ms 84940 KB Output is correct
12 Correct 322 ms 83400 KB Output is correct
13 Correct 39 ms 65860 KB Output is correct
14 Correct 320 ms 79580 KB Output is correct
15 Correct 85 ms 67012 KB Output is correct
16 Correct 932 ms 84140 KB Output is correct
17 Correct 339 ms 83604 KB Output is correct
18 Correct 342 ms 83680 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65860 KB Output is correct
2 Correct 41 ms 66012 KB Output is correct
3 Correct 41 ms 65992 KB Output is correct
4 Correct 47 ms 66168 KB Output is correct
5 Correct 43 ms 66168 KB Output is correct
6 Correct 42 ms 66124 KB Output is correct
7 Correct 38 ms 65936 KB Output is correct
8 Correct 303 ms 79512 KB Output is correct
9 Correct 260 ms 73044 KB Output is correct
10 Correct 642 ms 83900 KB Output is correct
11 Correct 339 ms 85012 KB Output is correct
12 Correct 336 ms 83332 KB Output is correct
13 Correct 38 ms 65860 KB Output is correct
14 Correct 320 ms 79532 KB Output is correct
15 Correct 86 ms 67100 KB Output is correct
16 Correct 930 ms 84236 KB Output is correct
17 Correct 344 ms 83572 KB Output is correct
18 Correct 335 ms 83524 KB Output is correct
19 Correct 741 ms 102312 KB Output is correct
20 Correct 685 ms 99788 KB Output is correct
21 Correct 683 ms 102212 KB Output is correct
22 Correct 668 ms 99780 KB Output is correct
23 Correct 687 ms 99920 KB Output is correct
24 Correct 678 ms 99780 KB Output is correct
25 Correct 669 ms 99780 KB Output is correct
26 Correct 673 ms 102212 KB Output is correct
27 Correct 702 ms 102252 KB Output is correct
28 Correct 675 ms 99724 KB Output is correct
29 Correct 677 ms 99896 KB Output is correct
30 Correct 677 ms 99840 KB Output is correct