oj.uz

Submission #65323

# Submission time Handle Problem Language Result Execution time Memory
65323 2018-08-07T11:30:31 Z gnoor Wall (IOI14_wall) C++17
61 / 100
 1390 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) {
		if (l+1!=r) {
			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) {
		if (l+1!=r) {
			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 143 ms 156884 KB Output is correct
2 Correct 130 ms 157164 KB Output is correct
3 Correct 136 ms 157164 KB Output is correct
4 Correct 149 ms 157276 KB Output is correct
5 Correct 153 ms 157532 KB Output is correct
6 Correct 143 ms 157564 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 157564 KB Output is correct
2 Correct 381 ms 170000 KB Output is correct
3 Correct 473 ms 170000 KB Output is correct
4 Correct 1147 ms 171048 KB Output is correct
5 Correct 488 ms 171592 KB Output is correct
6 Correct 525 ms 171592 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 171592 KB Output is correct
2 Correct 142 ms 171592 KB Output is correct
3 Correct 151 ms 171592 KB Output is correct
4 Correct 135 ms 171592 KB Output is correct
5 Correct 130 ms 171592 KB Output is correct
6 Correct 127 ms 171592 KB Output is correct
7 Correct 132 ms 171592 KB Output is correct
8 Correct 356 ms 171592 KB Output is correct
9 Correct 467 ms 171592 KB Output is correct
10 Correct 1147 ms 171592 KB Output is correct
11 Correct 482 ms 171592 KB Output is correct
12 Correct 446 ms 171592 KB Output is correct
13 Correct 141 ms 171592 KB Output is correct
14 Correct 332 ms 171592 KB Output is correct
15 Correct 180 ms 171592 KB Output is correct
16 Correct 1274 ms 171592 KB Output is correct
17 Correct 484 ms 171592 KB Output is correct
18 Correct 487 ms 180408 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 180408 KB Output is correct
2 Correct 139 ms 180408 KB Output is correct
3 Correct 136 ms 180408 KB Output is correct
4 Correct 152 ms 180408 KB Output is correct
5 Correct 156 ms 180408 KB Output is correct
6 Correct 132 ms 180408 KB Output is correct
7 Correct 126 ms 180408 KB Output is correct
8 Correct 325 ms 185292 KB Output is correct
9 Correct 487 ms 185292 KB Output is correct
10 Correct 1026 ms 190628 KB Output is correct
11 Correct 462 ms 191184 KB Output is correct
12 Correct 476 ms 191200 KB Output is correct
13 Correct 133 ms 191200 KB Output is correct
14 Correct 343 ms 191200 KB Output is correct
15 Correct 206 ms 191200 KB Output is correct
16 Correct 1390 ms 191200 KB Output is correct
17 Correct 473 ms 191200 KB Output is correct
18 Correct 442 ms 191200 KB Output is correct
19 Correct 882 ms 215344 KB Output is correct
20 Correct 1014 ms 223296 KB Output is correct
21 Correct 1209 ms 236240 KB Output is correct
22 Correct 1027 ms 244296 KB Output is correct
23 Correct 1008 ms 254716 KB Output is correct
24 Runtime error 1139 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
25 Halted 0 ms 0 KB -