oj.uz

Submission #13524

# Submission time Handle Problem Language Result Execution time Memory
13524 2015-02-23T01:13:01 Z Hyperbolic Wall (IOI14_wall) C++
0 / 100
 189 ms 67504 KB 
#include <stdio.h>
#include "wall.h"
struct str{
	int left;
	int right;
}x[5000010];
int check[5000010];
void func(int k, int left, int right, int type, int height)
{
	if(left<=x[k].left&&x[k].right<=right)
	{
		if(type==1) check[k]=check[k]>height?check[k]:height;
		else check[k]=check[k]<height?check[k]:height;
		return;
	}
	if(right<x[k].left) return;
	if(x[k].right<left) return;
	check[2*k]=check[k];
	check[2*k+1]=check[k];
	check[k]=-1;
	func(2*k,left,right,type,height);
	func(2*k+1,left,right,type,height);
}
int find(int k, int target)
{
	if(check[k]==-1)
	{
		if(x[2*k].left<=target&&target<=x[2*k].right) return find(2*k,target);
		else return find(2*k+1,target);
	}
	else return check[k];
}
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};
	for(i=C-1;i>=1;i--)
	{
		x[i]={x[2*i].left,x[2*i+1].right};
	}
	for(i=0;i<k;i++)
	{
		a=op[i];
		b=height[i];
		L=left[i];
		R=right[i];
		func(1,C+L,C+R,a,b);
	}
	for(i=0;i<n;i++)
	{
		finalheight[i]=find(1,i+C);
	}
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 59680 KB Output is correct
2 Correct 0 ms 59680 KB Output is correct
3 Incorrect 0 ms 59680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 59680 KB Output is correct
2 Correct 112 ms 67504 KB Output is correct
3 Incorrect 189 ms 62928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 59680 KB Output is correct
2 Correct 0 ms 59680 KB Output is correct
3 Incorrect 0 ms 59680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 59680 KB Output is correct
2 Correct 2 ms 59680 KB Output is correct
3 Incorrect 0 ms 59680 KB Output isn't correct
4 Halted 0 ms 0 KB -