제출 #97363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97363		fefe	벽 (IOI14_wall)	C++17	100 / 100	1658 ms	120568 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#define MAX_N 2000005
#define inf 1000005
using namespace std;
struct Tree{
	int l,r,x;
}t[4*MAX_N];
void add(int x,int v,int b){
	if(b==1){
		if(v<=t[x].l)	return;
		if(t[x].l<v && t[x].r>v){
			t[x].l=v;
			t[x].x=1;
			return;
		}
		t[x].l=t[x].r=v;
		t[x].x=0;
	}else{
		if(t[x].r<=v)	return;
		if(t[x].l<=v && t[x].r>v){
			t[x].r=v;
			t[x].x=0;
			return;
		}
		t[x].l=t[x].r=v;
		t[x].x=1;
	}
}
void spread(int x,int y){
	if(t[x].x){
		add(y,t[x].l,1);
		add(y,t[x].r,2);
	}else{
		add(y,t[x].r,2);
		add(y,t[x].l,1);
	}
}
void update(int x,int l,int r,int s,int e,int v,int b){
	if(l!=r){
		spread(x,2*x);
		spread(x,2*x+1);
		t[x]={0,inf,0};
	}
	if(e<l || r<s)	return;
	if(s<=l && r<=e){
		add(x,v,b);
		return;
	}
	int mid=(l+r)>>1;
	update(2*x,l,mid,s,e,v,b);
	update(2*x+1,mid+1,r,s,e,v,b);
}
int calc(int x,int v,int b){
	if(b==1)	return (x<v?v:x);
	else	return (x>v?v:x);
}
int get(int x,int l,int r,int p){
	if(l==r)	return t[x].l;
	int mid=(l+r)>>1,q;
	if(p<=mid)	q=get(2*x,l,mid,p);	
	else	q=get(2*x+1,mid+1,r,p);
	if(t[x].x==0)	q=calc(calc(q,t[x].l,1),t[x].r,2);
	else	q=calc(calc(q,t[x].r,2),t[x].l,1);
	return q;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int i;
	for(i=0;i<=4*n;i++)	t[i]={0,inf,0};
	for(i=0;i<k;i++){
		update(1,0,n-1,left[i],right[i],height[i],op[i]);
	}
	for(i=0;i<n;i++)	finalHeight[i]=get(1,0,n-1,i);
	return;
}

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