Submission #16748

#	Time	Username	Problem	Language	Result	Execution time	Memory
16748		choyi0521	Wall (IOI14_wall)	C++98	100 / 100	1625 ms	79224 KiB

wall

#include "wall.h"
#include<algorithm>
using namespace std;
const int MAX_N=2000000;
struct st{
	int mini,maxi;
	st():mini(0),maxi(0x7fffffff){}
}tree[MAX_N*4];
void update(int now,int l,int r,int gl,int gr,int op,int h){
	if(r<gl||gr<l) return;
	if(gl<=l&&r<=gr){
		if(op==1){
			tree[now].mini=max(tree[now].mini,h);
			tree[now].maxi=max(tree[now].mini,tree[now].maxi);
		}
		else{
			tree[now].maxi=min(tree[now].maxi,h);
			tree[now].mini=min(tree[now].mini,tree[now].maxi);
		}
		return;
	}
	tree[now*2+1].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+1].mini));
	tree[now*2+1].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+1].maxi));
	tree[now*2+2].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+2].mini));
	tree[now*2+2].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+2].maxi));
	tree[now].mini=0;
	tree[now].maxi=0x7fffffff;
	update(now*2+1,l,(l+r)/2,gl,gr,op,h);
	update(now*2+2,(l+r)/2+1,r,gl,gr,op,h);
}
int f(int now,int l,int r,int g){
	if(r<g||g<l) return 0;
	if(l==r) return tree[now].mini;
	tree[now*2+1].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+1].mini));
	tree[now*2+1].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+1].maxi));
	tree[now*2+2].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+2].mini));
	tree[now*2+2].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+2].maxi));
	tree[now].mini=0;
	tree[now].maxi=0x7fffffff;
	return max(f(now*2+1,l,(l+r)/2,g),f(now*2+2,(l+r)/2+1,r,g));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0; i<k; i++)
		update(0,0,n-1,left[i],right[i],op[i],height[i]);
	for(int i=0; i<n; i++)
		finalHeight[i]=f(0,0,n-1,i);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39