oj.uz

Submission #126533

# Submission time Handle Problem Language Result Execution time Memory
126533 2019-07-08T03:26:00 Z zozder Wall (IOI14_wall) C++14
8 / 100
 3000 ms 32652 KB 
#include "wall.h"
#include <iostream>
using namespace std;

int tree[1000000][6],o;
int ans[2000000];

/*
0	left
1	right
2	left link point
3	right link pint
4	value
5	cut_(mid)_put
*/
void add_tree(int x, int l, int r, int h, int count)
{
	count+=tree[x][4];
	int cutpoint = tree[x][5];
	if(tree[x][2]!=-1)
	{
		if(cutpoint<l)
		{
			add_tree(tree[x][3], l, r, h, count);
		}
		else if(l<=cutpoint&&cutpoint<r)
		{
			add_tree(tree[x][2], l, cutpoint, h, count);
			add_tree(tree[x][3], cutpoint+1, r, h, count);
		}
		else if(r<=cutpoint)
		{
			add_tree(tree[x][2], l, r, h, count);
		}
	}
	else
	{
		if(l!=tree[x][0]||r!=tree[x][1])
		{
			if(tree[x][0]<l)//xl..l...r...xr
			{
				cutpoint=l-1;
				tree[x][5]=cutpoint;
				o++;//左子樹 
				tree[x][2]=o;
				tree[o][0]=tree[x][0];
				tree[o][1]=cutpoint;
				tree[o][4]=0;
				o++;//右子樹 
				tree[x][3]=o;
				tree[o][0]=cutpoint+1;
				tree[o][1]=tree[x][1];
				tree[o][4]=0;
				add_tree(tree[x][3], l, r, h, count);
			}
			else if(tree[x][1]>r)//xll...r...xr
			{
				cutpoint=r;
				tree[x][5]=cutpoint;
				o++;//左子樹
				tree[x][2]=o;
				tree[o][0]=tree[x][0];
				tree[o][1]=cutpoint;
				tree[o][4]=0;
				add_tree(tree[x][2], l, r, h, count);
				o++;//右子樹
				tree[x][3]=o;
				tree[o][0]=cutpoint+1;
				tree[o][1]=tree[x][1];
				tree[o][4]=0;
			}
			
		}
		else // xll...rxr
		{
			if(count<h)
			tree[x][4]+=(h-count);
		}
	}
}

void down_tree(int x, int l, int r, int h, int count)
{
	count+=tree[x][4];//cout<<"x:"<<x<<"\t"<<"count:"<<count<<endl;
	int cutpoint = tree[x][5];
	if(tree[x][2]!=-1)
	{
		if(cutpoint<l)
		{
			down_tree(tree[x][3], l, r, h, count);
		}
		else if(l<=cutpoint&&cutpoint<r)
		{
			down_tree(tree[x][2], l, cutpoint, h, count);
			down_tree(tree[x][3], cutpoint+1, r, h, count);
		}
		else if(r<=cutpoint)
		{
			down_tree(tree[x][2], l, r, h, count);
		}
	}
	else
	{
		if(l!=tree[x][0]||r!=tree[x][1])
		{
			if(tree[x][0]<l)//xl..l...r...xr
			{
				cutpoint=l-1;
				tree[x][5]=cutpoint;
				o++;//左子樹 
				tree[x][2]=o;
				tree[o][0]=tree[x][0];
				tree[o][1]=cutpoint;
				tree[o][4]=0;
				o++;//右子樹 
				tree[x][3]=o;
				tree[o][0]=cutpoint+1;
				tree[o][1]=tree[x][1];
				tree[o][4]=0;
				down_tree(tree[x][3], l, r, h, count);
			}
			else if(tree[x][1]>r)//xll...r...xr
			{
				cutpoint=r;
				tree[x][5]=cutpoint;
				o++;//左子樹
				tree[x][2]=o;
				tree[o][0]=tree[x][0];
				tree[o][1]=cutpoint;
				tree[o][4]=0;
				down_tree(tree[x][2], l, r, h, count);
				o++;//右子樹
				tree[x][3]=o;
				tree[o][0]=cutpoint+1;
				tree[o][1]=tree[x][1];
				tree[o][4]=0;
			}
			
		}
		else // xll...rxr
		{
			if(count>h)
			tree[x][4]+=(h-count);
			//if(l==4&&r==8)cout<<count<<endl;
		}
	}
}

void pop_tree(int x,int count)
{
	count+=tree[x][4];//cout<<"count:"<<count<<endl;
	if(tree[x][2]!=-1)
	{
		pop_tree(tree[x][2], count);
		pop_tree(tree[x][3], count);
	}
	else
	{
		for(int i=tree[x][0];i<=tree[x][1];i++)ans[i]=count;
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<999999;i++)
	{
		tree[i][0]=-1;
		tree[i][1]=-1;
		tree[i][2]=-1;
		tree[i][3]=-1;
		tree[i][4]=0;
		tree[i][5]=-1;
	}
	
	tree[1][0]=0;
	tree[1][1]=n-1;
	tree[1][2]=-1;
	tree[1][3]=-1;
	tree[1][4]=0;
	tree[1][5]=-1;
	o=1;
	
	for(int i=0;i<k;i++)
	{
		//1up 2down
		if(op[i]==1)add_tree(1,left[i],right[i],height[i],0);
		else down_tree(1,left[i],right[i],height[i],0);
	}
	
	pop_tree(1,0);
	
	for(int i=0;i<n;i++)finalHeight[i]=ans[i];
/*	
	for(int i=1;i<=o;i++)cout<<i<<"\t";cout<<endl;
	for(int i=1;i<=o;i++)cout<<tree[i][0]<<"\t";cout<<endl;
	for(int i=1;i<=o;i++)cout<<tree[i][1]<<"\t";cout<<endl;
	for(int i=1;i<=o;i++)cout<<tree[i][2]<<"\t";cout<<endl;
	for(int i=1;i<=o;i++)cout<<tree[i][3]<<"\t";cout<<endl;
	for(int i=1;i<=o;i++)cout<<tree[i][4]<<"\t";cout<<endl;
	for(int i=1;i<=o;i++)cout<<tree[i][5]<<"\t";cout<<endl;
*/	
	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 25 ms 23800 KB Output is correct
4 Correct 165 ms 24064 KB Output is correct
5 Correct 129 ms 24184 KB Output is correct
6 Correct 128 ms 24312 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 193 ms 32652 KB Output is correct
3 Execution timed out 3034 ms 28152 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 23 ms 23932 KB Output is correct
3 Correct 25 ms 23976 KB Output is correct
4 Correct 163 ms 23968 KB Output is correct
5 Correct 127 ms 24128 KB Output is correct
6 Correct 129 ms 24184 KB Output is correct
7 Correct 22 ms 23800 KB Output is correct
8 Correct 191 ms 31736 KB Output is correct
9 Execution timed out 3054 ms 27200 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 27 ms 23928 KB Output is correct
3 Correct 25 ms 23800 KB Output is correct
4 Correct 168 ms 23968 KB Output is correct
5 Correct 127 ms 24184 KB Output is correct
6 Correct 128 ms 24056 KB Output is correct
7 Correct 22 ms 23800 KB Output is correct
8 Correct 191 ms 31708 KB Output is correct
9 Execution timed out 3036 ms 27128 KB Time limit exceeded
10 Halted 0 ms 0 KB -