Submission #13541

#	Time	Username	Problem	Language	Result	Execution time	Memory
13541		Hyperbolic	Wall (IOI14_wall)	C++98	100 / 100	1187 ms	94852 KiB

wall

#include <stdio.h>
#include "wall.h"
struct str{
	int left;
	int right;
}x[5000010],check[5000010];
int max(int a, int b)
{
	return a>b?a:b;
}
int min(int a, int b)
{
	return a<b?a:b;
}
void func(int k, int left, int right, int h_lower, int h_upper)
{
	if(x[k].right<left) return;
	if(x[k].left>right) return;
	if(left<=x[k].left&&x[k].right<=right)
	{
		if(check[k].right<h_lower) check[k]={h_lower,h_lower};
		else if(check[k].left>h_upper) check[k]={h_upper,h_upper};
		else check[k]={max(check[k].left,h_lower),min(check[k].right,h_upper)};
		return;
	}
	func(2*k,x[2*k].left,x[2*k].right,check[k].left,check[k].right);
	func(2*k+1,x[2*k+1].left,x[2*k+1].right,check[k].left,check[k].right);
	check[k]={0,100000};
	func(2*k,left,right,h_lower,h_upper);
	func(2*k+1,left,right,h_lower,h_upper);
}
int find(int k)
{
	str a={0,100000};
	while(k)
	{
		if(check[k].right<a.left) a={check[k].right,check[k].right};
		else if(check[k].left>a.right) a={check[k].left,check[k].left};
		else a={max(check[k].left,a.left),min(check[k].right,a.right)};
		k/=2;
	}
	return a.left;
}
void buildWall(int n, int k, int op[],int left[],int right[], int height[],int finalheight[])
{
	int C,i,a,b,L,R;
	for(C=1;C<n;C*=2);
	for(i=C;i<2*C;i++) x[i]={i,i},check[i]={0,0};
	for(i=C-1;i>=1;i--)
	{
		x[i]={x[2*i].left,x[2*i+1].right};
		check[i]={0,100000};
	}
	for(i=0;i<k;i++)
	{
		a=op[i];
		b=height[i];
		L=left[i];
		R=right[i];
		if(a==1) func(1,C+L,C+R,b,100000);
		else func(1,C+L,C+R,0,b);
		//func(1,C+L,C+R,a,b);
		//for(int j=0;j<n;j++)
		//{
			//printf("%d : %d\n",j,find(j+C));
		//}
		//printf("-------------------------\n");
	}
	for(i=0;i<n;i++)
	{
		finalheight[i]=find(i+C);
		//printf("%d : %d\n",i,finalheight[i]);
	}
}
/*int x1[110],x2[110],x3[110],x4[110],y[110];
int main()
{
	int a,b,i;
	scanf("%d%d",&a,&b);
	for(i=0;i<b;i++)
	{
		scanf("%d%d%d%d",&x1[i],&x2[i],&x3[i],&x4[i]);
	}
	buildWall(a,b,x1,x2,x3,x4,y);
}*/

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