제출 #416957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416957		vanic	벽 (IOI14_wall)	C++14	100 / 100	932 ms	102312 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39