제출 #1082521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082521		4QT0R	벽 (IOI14_wall)	C++17	100 / 100	552 ms	69464 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define pii pair<int,int>

const int base=1<<21;
pii tree[2*base];

void lazy_prop(int v){
	if (v>=base)return;
	if (tree[v].first>=tree[2*v].second)tree[2*v]={tree[v].first,tree[v].first};
	else if (tree[v].second<=tree[2*v].first)tree[2*v]={tree[v].second,tree[v].second};
	else{
		tree[2*v].first=max(tree[2*v].first,tree[v].first);
		tree[2*v].second=min(tree[2*v].second,tree[v].second);
	}
	if (tree[v].first>=tree[2*v+1].second)tree[2*v+1]={tree[v].first,tree[v].first};
	else if (tree[v].second<=tree[2*v+1].first)tree[2*v+1]={tree[v].second,tree[v].second};
	else{
		tree[2*v+1].first=max(tree[2*v+1].first,tree[v].first);
		tree[2*v+1].second=min(tree[2*v+1].second,tree[v].second);
	}
}

void update(int v, int l, int p, int a, int b, pii op){
	if (a<=l && p<=b){
		if (op.first==1){
			tree[v].first=max(tree[v].first,op.second);
			tree[v].second=max(tree[v].second,tree[v].first);
		}
		else{
			tree[v].second=min(tree[v].second,op.second);
			tree[v].first=min(tree[v].second,tree[v].first);
		}
		lazy_prop(v);
		return;
	}
	else if (p<a || b<l){
		lazy_prop(v);
		return;
	}
	else{
		lazy_prop(v);
		update(2*v,l,(l+p)/2,a,b,op);
		update(2*v+1,(l+p)/2+1,p,a,b,op);
		tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
	}
}

void finalProp(int v){
	if (v>=base)return;
	lazy_prop(v);
	finalProp(2*v);
	finalProp(2*v+1);
}

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
	for (int i = 0; i<k; i++)update(1,0,base-1,left[i],right[i],{op[i],height[i]});
	finalProp(1);
	for (int i = 0; i<n; i++)finalHeight[i]=tree[base+i].first;
}

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