제출 #413365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413365		Antekb	Wall (IOI14_wall)	C++14	100 / 100	842 ms	69488 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

const int N=(1<<21);
const int INF=1e9;
int tl[N+N], tr[N+N];
void prop(int v){
	if(v>=N)return;
	int l=v+v, r=l+1;
	tl[l]=min(max(tl[l], tl[v]), tr[v]);
	tl[r]=min(max(tl[r], tl[v]), tr[v]);
	tr[l]=max(min(tr[l], tr[v]), tl[v]);
	tr[r]=max(min(tr[r], tr[v]), tl[v]);
	tl[v]=-INF;
	tr[v]=INF;
}
void upd1(int v, int L, int R, int l, int r, int c){
	if(L==l && r==R){
		tr[v]=min(tr[v], c);
		tl[v]=min(tl[v], c);
		return;
	}
	prop(v);
	int M=(L+R)>>1;
	if(l<=M)upd1(2*v, L, M, l, min(r, M), c);
	if(r>M)upd1(2*v+1, M+1, R, max(l, M+1), r, c);
	return;
}
void upd2(int v, int L, int R, int l, int r, int c){
	if(L==l && r==R){
		tr[v]=max(tr[v], c);
		tl[v]=max(tl[v], c);
		return;
	}
	prop(v);
	int M=(L+R)>>1;
	if(l<=M)upd2(2*v, L, M, l, min(r, M), c);
	if(r>M)upd2(2*v+1, M+1, R, max(l, M+1), r, c);
	return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0; i<N; i++){
		tr[i]=INF;
		tl[i]=-INF;
	}
	for(int i=0; i<k; i++){
		if(op[i]==1)upd2(1, 0, N-1, left[i], right[i], height[i]);
		else upd1(1, 0, N-1, left[i], right[i], height[i]);
	}
	for(int i=1; i<N; i++){
		prop(i);
	}
	for(int i=0; i<n; i++){
		finalHeight[i]=tl[i+N];
	}
	return;
}

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