oj.uz

Submission #126522

# Submission time Handle Problem Language Result Execution time Memory
126522 2019-07-08T03:04:17 Z StevenH Wall (IOI14_wall) C++14
100 / 100
 790 ms 71696 KB 
#include "wall.h"
#include <iostream>
using namespace std;
int nn;
const int maxn = 2000005;
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(y<tx || ty<x)return ;
	if(tx<=x && y<=ty)	// xy在txty中 
	{
		if(h>=wall[p].max)	// 高度大於區間最高值 全部改 
		{
			wall[p].max=h; 
			wall[p].min=h;
			wall[p].val=h;
			return ;
		}
		else if(h<wall[p].min)return ;//高度小於區間最小 
	}
	if(wall[p].max == wall[p].min)
	{
		wall[p*2].max=wall[p*2+1].max=wall[p].max;
		wall[p*2].min=wall[p*2+1].min=wall[p].min;
		wall[p*2].val=wall[p*2+1].val=wall[p].val;
		wall[p].val=0;
	}
	add(p*2,x,mid,tx,ty,h);
	add(p*2+1,mid+1,y,tx,ty,h);
	wall[p].max=max(wall[p*2].max,wall[p*2+1].max);
	wall[p].min=min(wall[p*2].min,wall[p*2+1].min);
	return ;
}
void rmv(int p,int x,int y,int tx,int ty,int h)
{
	int mid=(x+y)/2;
	if(y<tx || ty<x)return ;
	if(tx<=x && y<=ty)	// xy在txty中 
	{
		if(h<=wall[p].min)	// 高度小於區間最低值 全部改 
		{
			wall[p].max=h; 
			wall[p].min=h;
			wall[p].val=h;
			return ;
		}
		else if(h>wall[p].max)return ;//高度大於區間最大 捨去 
	}
	if(wall[p].max == wall[p].min)
	{
		wall[p*2].max=wall[p*2+1].max=wall[p].max;
		wall[p*2].min=wall[p*2+1].min=wall[p].min;
		wall[p*2].val=wall[p*2+1].val=wall[p].val;
		wall[p].val=0;
	}
	rmv(p*2,x,mid,tx,ty,h);
	rmv(p*2+1,mid+1,y,tx,ty,h);	
	wall[p].max=max(wall[p*2].max,wall[p*2+1].max);
	wall[p].min=min(wall[p*2].min,wall[p*2+1].min);
	return ;
}
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)rmv(1,0,n-1,left[i],right[i],height[i]);	
		//find(1,0,n-1);
		//for (int j=0;j<n;j++)printf("%d ", fh[j]);
		//cout<<endl;
	}
  	find(1,0,n-1);
  	for(int i=0;i<n;i++)finalHeight[i]=fh[i];
  	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 9 ms 888 KB Output is correct
5 Correct 7 ms 892 KB Output is correct
6 Correct 7 ms 892 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 171 ms 8156 KB Output is correct
3 Correct 190 ms 4700 KB Output is correct
4 Correct 551 ms 12264 KB Output is correct
5 Correct 335 ms 13572 KB Output is correct
6 Correct 326 ms 13560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 172 ms 8184 KB Output is correct
9 Correct 198 ms 4644 KB Output is correct
10 Correct 790 ms 12256 KB Output is correct
11 Correct 334 ms 13560 KB Output is correct
12 Correct 323 ms 13560 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 177 ms 8952 KB Output is correct
15 Correct 37 ms 2296 KB Output is correct
16 Correct 673 ms 13396 KB Output is correct
17 Correct 319 ms 13304 KB Output is correct
18 Correct 327 ms 13304 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 448 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 172 ms 8184 KB Output is correct
9 Correct 189 ms 4560 KB Output is correct
10 Correct 556 ms 12264 KB Output is correct
11 Correct 337 ms 13544 KB Output is correct
12 Correct 323 ms 13544 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 177 ms 8952 KB Output is correct
15 Correct 37 ms 2352 KB Output is correct
16 Correct 665 ms 13244 KB Output is correct
17 Correct 320 ms 13448 KB Output is correct
18 Correct 324 ms 13308 KB Output is correct
19 Correct 750 ms 71696 KB Output is correct
20 Correct 754 ms 69240 KB Output is correct
21 Correct 742 ms 71460 KB Output is correct
22 Correct 753 ms 69020 KB Output is correct
23 Correct 765 ms 68984 KB Output is correct
24 Correct 734 ms 69192 KB Output is correct
25 Correct 736 ms 68984 KB Output is correct
26 Correct 746 ms 71444 KB Output is correct
27 Correct 747 ms 71544 KB Output is correct
28 Correct 742 ms 68984 KB Output is correct
29 Correct 738 ms 69084 KB Output is correct
30 Correct 736 ms 69012 KB Output is correct