제출 #369459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369459		pure_mem	벽 (IOI14_wall)	C++14	100 / 100	850 ms	140224 KiB

wall

#include "wall.h"
#include <utility>
#include <algorithm>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int N = 2e6 + 12;
const int INF = 1e6;

pair<int, int> t[N * 4], tt[N * 4];
int fin[N];

pair<int, int> merge(pair<int, int> x, pair<int, int> y){
	if(y == MP(0, INF))
		return x;
	if(y.Y <= x.X)
		return MP(x.X, x.X);
	if(x.Y <= y.X)
		return MP(x.Y, x.Y);
	if(x.X <= y.X && y.X <= x.Y)
		x.X = y.X;
	if(x.X <= y.Y && y.Y <= x.Y)
		x.Y = y.Y;
	return x;
}

void push(int v){
	if(tt[v] == MP(0, INF))
		return;
	t[v * 2] = merge(tt[v], t[v * 2]);
	tt[v * 2] = merge(tt[v], tt[v * 2]);
	t[v * 2 + 1] = merge(tt[v], t[v * 2 + 1]);
	tt[v * 2 + 1] = merge(tt[v], tt[v * 2 + 1]);
	tt[v] = MP(0, INF); 
}

void upd(int v, int tl, int tr, int l, int r, pair<int, int> val){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		tt[v] = merge(val, tt[v]), t[v] = merge(val, t[v]);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
}

void solve(int v, int tl, int tr){
	if(tl == tr){
		fin[tl] = t[v].X;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	solve(v * 2, tl, tm), solve(v * 2 + 1, tm + 1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 1;i <= n * 4;i++)
		tt[i] = MP(0, INF);
	for(int i = 0;i < k;i++){
		if(op[i] == 1){
			upd(1, 1, n, left[i] + 1, right[i] + 1, MP(height[i], INF));
		}
		else{
		    upd(1, 1, n, left[i] + 1, right[i] + 1, MP(0, height[i]));
		}
	}
	solve(1, 1, n);
	for(int i = 1;i <= n;i++)
		finalHeight[i - 1] = fin[i];
}

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