제출 #52101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52101		spencercompton	벽 (IOI14_wall)	C++17	100 / 100	1681 ms	393216 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int inf = 100000;
int low[4194304];
int high[4194304];
int l[4194304];
int r[4194304];
int point = 0;
int create(int s, int e){
	int now = point++;
	if(s==e){
		l[now] = -1;
		r[now] = -1;
		low[now] = 0;
		high[now] = 0;
	}
	else{
		int lv = create(s,(s+e)/2);
		l[now] = lv;
		int rv = create((s+e)/2+1,e);
		r[now] = rv;
		low[now] = 0;
		high[now] = 100000;
	}
	return now;
}
void push(int now, int nlow, int nhigh){
	if(nlow>=high[now]){
		high[now] = nlow;
		low[now] = nlow;
	}
	else if(nhigh<=low[now]){
		low[now] = nhigh;
		high[now] = nhigh;
	}
	else{
		high[now] = min(high[now],nhigh);
		low[now] = max(low[now],nlow);
	}
}
void upd(int now, int st, int en, int s, int e, int nlow, int nhigh){
	if(s==e){
		push(now,nlow,nhigh);
		return;
	}
	if(st<=s && e<=en){
		push(now,nlow,nhigh);
		return;
	}
	push(l[now],low[now],high[now]);
	push(r[now],low[now],high[now]);
	low[now] = 0;
	high[now] = inf;
	if(st<=(s+e)/2){
		upd(l[now],st,en,s,(s+e)/2,nlow,nhigh);
	}
	if(en>(s+e)/2){
		upd(r[now],st,en,(s+e)/2+1,e,nlow,nhigh);
	}
}
int get(int ind, int now, int s, int e){
	if(s==e){
		// cout << "@ " << s << " " << e << " " << low[now] << " " << high[now] << endl;
		assert(low[now]==high[now]);
		return low[now];
	}
	push(l[now],low[now],high[now]);
	push(r[now],low[now],high[now]);
	low[now] = 0;
	high[now] = inf;
	if(ind<=(s+e)/2){
		return get(ind,l[now],s,(s+e)/2);
	}
	else{
		return get(ind,r[now],(s+e)/2+1,e);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	// cout << "A " << endl;
	int t = create(0,n-1);
	// cout << "B " << endl;
	for(int i = 0; i<k; i++){
		// cout << "C " << i << " " << k << endl;
		if(op[i]==1){
			//add
			// cout << "!  " << t << " " << left[i] << " " << right[i] << " " << height[i] << endl;
			upd(t,left[i],right[i],0,n-1,height[i],inf);
		}
		else{
			//remove
			upd(t,left[i],right[i],0,n-1,0,height[i]);
		}
	}
	// cout << "D " << endl;
	for(int i = 0; i<n; i++){
		finalHeight[i] = get(i,t,0,n-1);
		// cout << "E " << i << " " << finalHeight[i] << endl;
	}
}

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