oj.uz

Submission #126516

# Submission time Handle Problem Language Result Execution time Memory
126516 2019-07-08T02:52:33 Z StevenH Wall (IOI14_wall) C++14
100 / 100
 770 ms 72580 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;
			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;
	}
	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;
			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;
	}
	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 i=0;i<n;i++)cout<<fh[i]<<" ";
  		//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 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 1016 KB Output is correct
5 Correct 7 ms 956 KB Output is correct
6 Correct 7 ms 992 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 171 ms 8312 KB Output is correct
3 Correct 184 ms 4808 KB Output is correct
4 Correct 565 ms 14568 KB Output is correct
5 Correct 329 ms 14840 KB Output is correct
6 Correct 319 ms 14844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 956 KB Output is correct
5 Correct 7 ms 1016 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 172 ms 10232 KB Output is correct
9 Correct 191 ms 6600 KB Output is correct
10 Correct 537 ms 14328 KB Output is correct
11 Correct 329 ms 14744 KB Output is correct
12 Correct 320 ms 14712 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 182 ms 10144 KB Output is correct
15 Correct 36 ms 2424 KB Output is correct
16 Correct 636 ms 14456 KB Output is correct
17 Correct 321 ms 14456 KB Output is correct
18 Correct 327 ms 14456 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 504 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 8 ms 1016 KB Output is correct
5 Correct 7 ms 1056 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 173 ms 9976 KB Output is correct
9 Correct 184 ms 6392 KB Output is correct
10 Correct 560 ms 14236 KB Output is correct
11 Correct 324 ms 14584 KB Output is correct
12 Correct 321 ms 14572 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 9976 KB Output is correct
15 Correct 37 ms 2552 KB Output is correct
16 Correct 655 ms 14172 KB Output is correct
17 Correct 321 ms 14200 KB Output is correct
18 Correct 329 ms 14256 KB Output is correct
19 Correct 761 ms 72568 KB Output is correct
20 Correct 740 ms 70264 KB Output is correct
21 Correct 750 ms 72580 KB Output is correct
22 Correct 748 ms 70128 KB Output is correct
23 Correct 741 ms 69956 KB Output is correct
24 Correct 740 ms 69916 KB Output is correct
25 Correct 750 ms 69752 KB Output is correct
26 Correct 748 ms 72284 KB Output is correct
27 Correct 749 ms 72440 KB Output is correct
28 Correct 737 ms 69732 KB Output is correct
29 Correct 770 ms 69660 KB Output is correct
30 Correct 752 ms 69400 KB Output is correct