제출 #138181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138181		junodeveloper	벽 (IOI14_wall)	C++14	0 / 100	203 ms	13952 KiB

wall

#include "wall.h"
#include <algorithm>
using namespace std;
struct node {
	int mx,mn;
} T[4*100010];
void apply(int h,int mn,int mx) {
	if(T[h].mx<mn) T[h].mx=T[h].mn=mn;
	else if(mx<T[h].mn) T[h].mx=T[h].mn=mx;
	else {
		T[h].mn=max(T[h].mn,mn);
		T[h].mx=min(T[h].mx,mx);
	}
}
void update(int h,int tl,int tr,int l,int r,int mn,int mx) {
	if(tr<l||r<tl)return;
	if(h>1)apply(h,T[h/2].mn,T[h/2].mx);
	if(l<=tl&&tr<=r) {
		apply(h,mn,mx);
		return;
	}
	int mid=(tl+tr)>>1;
	update(h*2,tl,mid,l,r,mn,mx);
	update(h*2+1,mid+1,tr,l,r,mn,mx);
	T[h].mn=min(T[h*2].mn,T[h*2+1].mn);
	T[h].mx=max(T[h*2].mx,T[h*2+1].mx);
}
int query(int h,int tl,int tr,int p){
	if(h>1)apply(h,T[h/2].mn,T[h/2].mx);
	if(tl==tr) return T[h].mn;
	int mid=(tl+tr)>>1;
	if(p<=mid) return query(h*2,tl,mid,p);
	return query(h*2+1,mid+1,tr,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	int i,mn,mx;
	for(i=0;i<=4*n;i++) T[i]={0,0};
	for(i=0;i<k;i++) {
		if(op[i]==1) mn=height[i],mx=1e9;
		else mn=0,mx=height[i];
		update(1,0,n-1,left[i],right[i],mn,mx);
	}
	for(i=0;i<n;i++) {
		finalHeight[i]=query(1,0,n-1,i);
	}
}

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