제출 #8581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8581		cki86201	벽 (IOI14_wall)	C++98	100 / 100	1120 ms	65880 KiB

wall

#include "wall.h"
#include<algorithm>
using namespace std;

int T[1<<22], P[1<<22], M[1<<22];

inline void update_node(int rt, int mode, int h){
	if(mode == 1){
		T[rt] = max(T[rt], h);
		P[rt] = max(P[rt], h);
		M[rt] = max(M[rt], P[rt]);
	}
	else{
		T[rt] = min(T[rt], h);
		M[rt] = min(M[rt], h);
		P[rt] = min(P[rt], M[rt]);
	}
}

void pushdown(int rt){
	update_node(rt<<1, 2, M[rt]);
	update_node(rt<<1, 1, P[rt]);
	update_node(rt<<1|1, 2, M[rt]);
	update_node(rt<<1|1, 1, P[rt]);
	P[rt] = 0, M[rt] = 1e5 + 5;
}

void update(int rt, int s, int d, int mode, int l, int r, int h){
	if(l <= s && d <= r){
		update_node(rt, mode, h);
		return;
	}
	pushdown(rt);
	int m = (s+d)>>1;
	if(l<=m)update(rt<<1, s, m, mode, l, r, h);
	if(m<r)update(rt<<1|1, m+1, d, mode, l, r, h);
}

void get_ans(int rt, int s, int d, int &cnt, int arr[]){
	if(s == d){
		arr[cnt++] = T[rt];
		return;
	}
	int m = (s+d)>>1;
	pushdown(rt);
	get_ans(rt<<1, s, m, cnt, arr);
	get_ans(rt<<1|1, m+1, d, cnt, arr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int i;
	for(i=0;i<1<<22;i++)M[i] = 1e5 + 5;
	for(i=0;i<k;i++)update(1, 0, n-1, op[i], left[i], right[i], height[i]);
	int cnt = 0;
	get_ans(1, 0, n-1, cnt, finalHeight);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39