oj.uz

Submission #13541

# Submission time Handle Problem Language Result Execution time Memory
13541 2015-02-23T11:50:52 Z Hyperbolic Wall (IOI14_wall) C++
100 / 100
 1187 ms 94852 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 79212 KB Output is correct
2 Correct 2 ms 79212 KB Output is correct
3 Correct 0 ms 79212 KB Output is correct
4 Correct 10 ms 79212 KB Output is correct
5 Correct 7 ms 79212 KB Output is correct
6 Correct 7 ms 79212 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 79212 KB Output is correct
2 Correct 177 ms 87036 KB Output is correct
3 Correct 276 ms 82460 KB Output is correct
4 Correct 733 ms 87428 KB Output is correct
5 Correct 466 ms 87428 KB Output is correct
6 Correct 470 ms 87428 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 79212 KB Output is correct
2 Correct 0 ms 79212 KB Output is correct
3 Correct 0 ms 79212 KB Output is correct
4 Correct 9 ms 79212 KB Output is correct
5 Correct 6 ms 79212 KB Output is correct
6 Correct 7 ms 79212 KB Output is correct
7 Correct 0 ms 79212 KB Output is correct
8 Correct 160 ms 87036 KB Output is correct
9 Correct 257 ms 82460 KB Output is correct
10 Correct 748 ms 87428 KB Output is correct
11 Correct 482 ms 87428 KB Output is correct
12 Correct 455 ms 87428 KB Output is correct
13 Correct 0 ms 79212 KB Output is correct
14 Correct 180 ms 87036 KB Output is correct
15 Correct 51 ms 79696 KB Output is correct
16 Correct 901 ms 87428 KB Output is correct
17 Correct 466 ms 87428 KB Output is correct
18 Correct 461 ms 87428 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 79212 KB Output is correct
2 Correct 0 ms 79212 KB Output is correct
3 Correct 0 ms 79212 KB Output is correct
4 Correct 9 ms 79212 KB Output is correct
5 Correct 7 ms 79212 KB Output is correct
6 Correct 7 ms 79212 KB Output is correct
7 Correct 0 ms 79212 KB Output is correct
8 Correct 171 ms 87036 KB Output is correct
9 Correct 285 ms 82460 KB Output is correct
10 Correct 752 ms 87428 KB Output is correct
11 Correct 550 ms 87428 KB Output is correct
12 Correct 512 ms 87428 KB Output is correct
13 Correct 0 ms 79212 KB Output is correct
14 Correct 177 ms 87036 KB Output is correct
15 Correct 50 ms 79696 KB Output is correct
16 Correct 890 ms 87428 KB Output is correct
17 Correct 493 ms 87428 KB Output is correct
18 Correct 467 ms 87428 KB Output is correct
19 Correct 1126 ms 94852 KB Output is correct
20 Correct 1127 ms 94852 KB Output is correct
21 Correct 1153 ms 94852 KB Output is correct
22 Correct 1097 ms 94852 KB Output is correct
23 Correct 1159 ms 94852 KB Output is correct
24 Correct 1155 ms 94852 KB Output is correct
25 Correct 1158 ms 94852 KB Output is correct
26 Correct 1147 ms 94852 KB Output is correct
27 Correct 1144 ms 94852 KB Output is correct
28 Correct 1102 ms 94852 KB Output is correct
29 Correct 1187 ms 94852 KB Output is correct
30 Correct 1159 ms 94852 KB Output is correct