Submission #12192

#	Time	Username	Problem	Language	Result	Execution time	Memory
12192		ho94949	Wall (IOI14_wall)	C++98	61 / 100	1148 ms	41300 KiB

wall

#include "wall.h"
#include <algorithm>
#define N 1048576
#define INF 987654321
int seg[2*N];
int minh[2*N];
int maxh[2*N];
void updatelazy(int ind){
	if(minh[ind]==-INF) return;
	seg[ind]=std::max(seg[ind],minh[ind]);
	seg[ind]=std::min(seg[ind],maxh[ind]);
	if(ind<N){
		if(maxh[2*ind]<minh[ind]) minh[2*ind]=maxh[2*ind]=minh[ind];
		if(maxh[ind]<minh[2*ind]) minh[2*ind]=maxh[2*ind]=maxh[ind];
		maxh[2*ind]=std::min(maxh[ind],maxh[2*ind]);
		minh[2*ind]=std::max(minh[ind],minh[2*ind]);
		if(maxh[2*ind+1]<minh[ind]) minh[2*ind+1]=maxh[2*ind+1]=minh[ind];
		if(maxh[ind]<minh[2*ind+1]) minh[2*ind+1]=maxh[2*ind+1]=maxh[ind];
		maxh[2*ind+1]=std::min(maxh[ind],maxh[2*ind+1]);
		minh[2*ind+1]=std::max(minh[ind],minh[2*ind+1]);
	}
	minh[ind]=-INF;
	maxh[ind]=INF;
	return;
}
void set(int ind,int indleft,int indright,int minv,int maxv,int left,int right){
	if(left<=indleft && indright <=right){
		if(maxh[ind]<minv) maxh[ind]=minh[ind]=minv;
		if(maxv<minh[ind]) minh[ind]=maxh[ind]=maxv;
		maxh[ind]=std::min(maxh[ind],maxv);
		minh[ind]=std::max(minh[ind],minv);
		updatelazy(ind);
		return;
	}
	updatelazy(ind);
	if(indright<left || right < indleft) return;
	if(ind<N){
		set(2*ind,indleft,(indleft+indright)/2,minv,maxv,left,right);
		set(2*ind+1,(indleft+indright)/2+1,indright,minv,maxv,left,right);
	}
	return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1;i<2*N;i++) minh[i]=-INF,maxh[i]=INF;
	for(int i=0;i<k;i++){
		if(op[i]==2) set(1,0,N-1,0,height[i],left[i],right[i]);
		else set(1,0,N-1,height[i],INF,left[i],right[i]);
	}
	for(int i=1;i<N+n;i++) updatelazy(i);
	for(int i=0;i<n;i++) finalHeight[i]=seg[N+i];
	return;
}

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