oj.uz

Submission #65314

# Submission time Handle Problem Language Result Execution time Memory
65314 2018-08-07T11:24:38 Z gnoor Wall (IOI14_wall) C++17
61 / 100
 3000 ms 263168 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 156920 KB Output is correct
2 Correct 134 ms 157164 KB Output is correct
3 Correct 147 ms 157164 KB Output is correct
4 Correct 142 ms 157308 KB Output is correct
5 Correct 141 ms 157440 KB Output is correct
6 Correct 141 ms 157596 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 157596 KB Output is correct
2 Correct 493 ms 169972 KB Output is correct
3 Correct 520 ms 169972 KB Output is correct
4 Correct 1264 ms 170944 KB Output is correct
5 Correct 491 ms 171496 KB Output is correct
6 Correct 481 ms 171496 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 171496 KB Output is correct
2 Correct 149 ms 171496 KB Output is correct
3 Correct 136 ms 171496 KB Output is correct
4 Correct 148 ms 171496 KB Output is correct
5 Correct 135 ms 171496 KB Output is correct
6 Correct 140 ms 171496 KB Output is correct
7 Correct 141 ms 171496 KB Output is correct
8 Correct 342 ms 171496 KB Output is correct
9 Correct 458 ms 171496 KB Output is correct
10 Correct 1115 ms 171496 KB Output is correct
11 Correct 497 ms 171496 KB Output is correct
12 Correct 464 ms 171532 KB Output is correct
13 Correct 127 ms 171532 KB Output is correct
14 Correct 349 ms 171532 KB Output is correct
15 Correct 191 ms 171532 KB Output is correct
16 Correct 1424 ms 171532 KB Output is correct
17 Correct 461 ms 171532 KB Output is correct
18 Correct 457 ms 180352 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 180352 KB Output is correct
2 Correct 129 ms 180352 KB Output is correct
3 Correct 125 ms 180352 KB Output is correct
4 Correct 138 ms 180352 KB Output is correct
5 Correct 145 ms 180352 KB Output is correct
6 Correct 137 ms 180352 KB Output is correct
7 Correct 136 ms 180352 KB Output is correct
8 Correct 355 ms 185360 KB Output is correct
9 Correct 543 ms 185360 KB Output is correct
10 Correct 1268 ms 199744 KB Output is correct
11 Correct 467 ms 210508 KB Output is correct
12 Correct 420 ms 219008 KB Output is correct
13 Correct 138 ms 219008 KB Output is correct
14 Correct 318 ms 223376 KB Output is correct
15 Correct 197 ms 223376 KB Output is correct
16 Correct 1482 ms 234844 KB Output is correct
17 Correct 496 ms 243968 KB Output is correct
18 Correct 515 ms 252888 KB Output is correct
19 Execution timed out 3048 ms 263168 KB Time limit exceeded
20 Halted 0 ms 0 KB -