제출 #125850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125850		StevenH	벽 (IOI14_wall)	C++14	0 / 100	167 ms	13944 KiB

wall

#include "wall.h"
const int maxn = 100005;
struct Wall{
	int max,min,val;
}wall[maxn*4];
int fh[maxn];
void add(int p,int x,int y,int tx,int ty,int h) 
{
	int mid=(x+y)/2;
	if(tx<=x && y<=ty)	// xy在txty中 
	{
		if(h>=wall[p].max)	// 高度大於區間最高值 全部改 
		{
			wall[p].max=h; 
			wall[p].min=h;
		}
		else if(h<wall[p].min)return ;//高度小於區間最小 
		else  
		{
			add(p*2,x,mid,tx,ty,h);
			add(p*2+1,mid+1,y,tx,ty,h);
		}
	}
	else
	{
		if(tx<=mid)add(p*2,x,mid,tx,ty,h);
		if(mid<=ty)add(p*2+1,mid+1,y,tx,ty,h);
	}
}
void rmv(int p,int x,int y,int tx,int ty,int h)
{
	int mid=(x+y)/2;
	if(tx<=x && y<=ty)	// xy在txty中 
	{
		if(h<=wall[p].min)	// 高度小於區間最低值 全部改 
		{
			wall[p].max=h; 
			wall[p].min=h;
		}
		else if(h>wall[p].max)return ;//高度大於區間最大 捨去 
		else  
		{
			rmv(p*2,x,mid,tx,ty,h);
			rmv(p*2+1,mid+1,y,tx,ty,h);
		}
	}
	else
	{
		if(tx<=mid)rmv(p*2,x,mid,tx,ty,h);
		if(mid<=ty)rmv(p*2+1,mid+1,y,tx,ty,h);
	}
}
void find(int p,int x,int y)
{
	if(wall[p].max==wall[p].min)
	{
		for(int i=x;i<=y;i++)fh[i]=wall[p].min;
		return ;
	}
	int mid=(x+y)/2;
	find(p*2,x,mid);
	find(p*2+1,mid+1,y);
	return ;
}
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)
		{
			add(1,0,n-1,left[i],right[i],height[i]);	
		}
		if(op[i]==2)
		{
			add(1,0,n-1,left[i],right[i],height[i]);	
		}
	}
  	find(1,0,n-1);
  	for(int i=0;i<n;i++)finalHeight[i]=fh[i];
  return;
}

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