제출 #347121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347121		ogibogi2004	벽 (IOI14_wall)	C++14	8 / 100	541 ms	262148 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6;
const int INF=2e8;
struct node
{
	int down,up;
	node()
	{
		down=INF;up=0;
	}
};
node tree[4*MAXN];
node update_d(node t,int h)
{
	t.down=min(t.down,h);
	t.up=min(t.up,t.down);
	return t;
}
node update_u(node t,int h)
{
	t.up=max(t.up,h);
	t.down=max(t.down,t.up);
	return t;
}
node update(node t1,node t2)
{
	t1.down=min(t1.down,t2.down);
	t1.up=max(t1.up,t2.up);
	t1.down=max(t1.down,t2.up);
	t1.up=min(t1.up,t2.down);
	return t1;
}
void push(int l,int r,int idx)
{
	if(tree[idx].down==INF&&tree[idx].up==0)return;
	if(l==r)return;
	tree[idx*2]=update(tree[idx*2],tree[idx]);
	tree[idx*2+1]=update(tree[idx*2+1],tree[idx]);
	tree[idx]=(*new node());
}
void update_d(int idx,int l,int r,int ql,int qr,int h)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		tree[idx]=update_d(tree[idx],h);
		push(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update_d(idx*2,l,mid,ql,qr,h);
	update_d(idx*2+1,mid+1,r,ql,qr,h);
}
void update_u(int idx,int l,int r,int ql,int qr,int h)
{
	push(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		tree[idx]=update_u(tree[idx],h);
		push(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update_u(idx*2,l,mid,ql,qr,h);
	update_u(idx*2+1,mid+1,r,ql,qr,h);
}
int ans1[4*MAXN];
void trav(int idx,int l,int r)
{
	push(l,r,idx);
	//cout<<l<<" "<<r<<" : "<<tree[idx].down<<" "<<tree[idx].up<<endl;
	if(l==r)
	{
		ans1[l]=min(tree[idx].down,tree[idx].up);
	}
	else
	{
		int mid=(l+r)/2;
		trav(idx*2,l,mid);
		trav(idx*2+1,mid+1,r);
	}
}
void trav1(int idx,int l,int r)
{
	cout<<l<<" "<<r<<" : "<<tree[idx].down<<" "<<tree[idx].up<<endl;
	//push(l,r,idx);
	if(l==r)
	{
		return;
	}
	else
	{
		int mid=(l+r)/2;
		trav1(idx*2,l,mid);
		trav1(idx*2+1,mid+1,r);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	for(int i=0;i<k;i++)
	{
		if(op[i]==1)
		{
			update_u(1,0,n-1,left[i],right[i],height[i]);
		}
		else
		{
			update_d(1,0,n-1,left[i],right[i],height[i]);
		}
		//trav1(1,0,n-1);
		//cout<<"---------------\n";
	}
	trav(1,0,n-1);
	for(int i=0;i<n;i++)finalHeight[i]=ans1[i];
}

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