Submission #65314

#	Time	Username	Problem	Language	Result	Execution time	Memory
65314		gnoor	Wall (IOI14_wall)	C++17	61 / 100	3048 ms	263168 KiB

wall

#include "wall.h"

struct node {
	int lo,hi;
	int lazylo,lazyhi;
	bool haslazy;

	node():lo(0),hi(1e9),lazylo(0),lazyhi(1e9),haslazy(false) {}
};

node seg[8000000];

int clamp (int v,int lo,int hi) {
	if (v<lo) return lo;
	if (v>hi) return hi;
	return v;
}

void update(int idx,int l,int r,int ll,int rr,int op,int val) {
	if (ll>=r||rr<=l) return;
	//expand lazy
	if (seg[idx].haslazy) {
		seg[idx*2+1].lazylo=clamp(seg[idx*2+1].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+1].lazyhi=clamp(seg[idx*2+1].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+1].haslazy=true;

		seg[idx*2+2].lazylo=clamp(seg[idx*2+2].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+2].lazyhi=clamp(seg[idx*2+2].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+2].haslazy=true;
		
		seg[idx].lo=clamp(seg[idx].lo,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx].hi=clamp(seg[idx].hi,seg[idx].lazylo,seg[idx].lazyhi);

		seg[idx].lazylo=0;
		seg[idx].lazyhi=1e9;
		seg[idx].haslazy=false;
	}
	//update
	if (ll<=l&&rr>=r) {
		if (op==1) {
			//adjust lo
			seg[idx].lazylo=clamp(seg[idx].lazylo,val,1e9);
			seg[idx].lazyhi=clamp(seg[idx].lazyhi,val,1e9);
		} else {
			//adjust hi
			seg[idx].lazyhi=clamp(seg[idx].lazyhi,0,val);
			seg[idx].lazylo=clamp(seg[idx].lazylo,0,val);
		}
		seg[idx].haslazy=true;
		return;
	}
	int m=(l+r)>>1;
	update(idx*2+1,l,m,ll,rr,op,val);
	update(idx*2+2,m,r,ll,rr,op,val);
}

int ans[2000100];

void getans(int idx,int l,int r) {
	if (seg[idx].haslazy) {
		seg[idx*2+1].lazylo=clamp(seg[idx*2+1].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+1].lazyhi=clamp(seg[idx*2+1].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+1].haslazy=true;

		seg[idx*2+2].lazylo=clamp(seg[idx*2+2].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+2].lazyhi=clamp(seg[idx*2+2].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx*2+2].haslazy=true;
		
		seg[idx].lo=clamp(seg[idx].lo,seg[idx].lazylo,seg[idx].lazyhi);
		seg[idx].hi=clamp(seg[idx].hi,seg[idx].lazylo,seg[idx].lazyhi);

		seg[idx].lazylo=0;
		seg[idx].lazyhi=1e9;
		seg[idx].haslazy=false;
	}
	if (l+1==r) {
		ans[l]=seg[idx].lo;
		return;
	}
	int m=(l+r)>>1;
	getans(idx*2+1,l,m);
	getans(idx*2+2,m,r);
}

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,left[i],right[i]+1,op[i],height[i]);
	}
	getans(0,0,n);
	for (int i=0;i<n;i++){
		finalHeight[i]=ans[i];
	}
}

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