oj.uz

답안 #126210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126210 2019-07-07T09:11:33 Z StevenH 벽 (IOI14_wall) C++14
8 / 100
 469 ms 12376 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 push_up(int p)
{
	//cout<<p<<endl;
	if(p>1)
	{
		int k=(p/2);
		wall[k].max=max(wall[k*2].max,wall[k*2+1].max);
		wall[k].min=min(wall[k*2].min,wall[k*2+1].min);
		push_up(p/2);
	}
}
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;
			push_up(p);
			return ;
		}
		else if(h<wall[p].min)return ;//高度小於區間最小 
	}
	if(wall[p].val)
	{
		wall[p*2].max=wall[p*2+1].max=wall[p].val;
		wall[p*2].min=wall[p*2+1].min=wall[p].val;
		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);
	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;
			push_up(p);
			return ;
		}
		else if(h>wall[p].max)return ;//高度大於區間最大 捨去 
	}
	if(wall[p].val)
	{
		wall[p*2].max=wall[p*2+1].max=wall[p].val;
		wall[p*2].min=wall[p*2+1].min=wall[p].val;
		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);
	return ;
}
void find(int p,int x,int y)
{
	if(wall[p].max==wall[p].min)
	{
		//cout<<x<<" "<<y<<endl;
		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)
		{
			//cout<<"*";
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 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 8 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 174 ms 8160 KB Output is correct
3 Correct 161 ms 4600 KB Output is correct
4 Incorrect 459 ms 12376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 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 8 ms 888 KB Output is correct
6 Correct 8 ms 888 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 164 ms 4612 KB Output is correct
10 Incorrect 461 ms 12328 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 9 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 173 ms 8184 KB Output is correct
9 Correct 163 ms 4728 KB Output is correct
10 Incorrect 469 ms 12364 KB Output isn't correct
11 Halted 0 ms 0 KB -