oj.uz

Submission #65321

# Submission time Handle Problem Language Result Execution time Memory
65321 2018-08-07T11:29:54 Z gnoor Wall (IOI14_wall) C++17
61 / 100
 1488 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 137 ms 156792 KB Output is correct
2 Correct 135 ms 156996 KB Output is correct
3 Correct 151 ms 157268 KB Output is correct
4 Correct 138 ms 157404 KB Output is correct
5 Correct 139 ms 157452 KB Output is correct
6 Correct 147 ms 157632 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 157632 KB Output is correct
2 Correct 385 ms 170204 KB Output is correct
3 Correct 462 ms 170204 KB Output is correct
4 Correct 1044 ms 171100 KB Output is correct
5 Correct 451 ms 171612 KB Output is correct
6 Correct 429 ms 171612 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 171612 KB Output is correct
2 Correct 129 ms 171612 KB Output is correct
3 Correct 138 ms 171612 KB Output is correct
4 Correct 137 ms 171612 KB Output is correct
5 Correct 131 ms 171612 KB Output is correct
6 Correct 149 ms 171612 KB Output is correct
7 Correct 135 ms 171612 KB Output is correct
8 Correct 369 ms 171612 KB Output is correct
9 Correct 583 ms 171612 KB Output is correct
10 Correct 1295 ms 171612 KB Output is correct
11 Correct 496 ms 171768 KB Output is correct
12 Correct 480 ms 171768 KB Output is correct
13 Correct 131 ms 171768 KB Output is correct
14 Correct 356 ms 171768 KB Output is correct
15 Correct 197 ms 171768 KB Output is correct
16 Correct 1488 ms 171768 KB Output is correct
17 Correct 551 ms 171768 KB Output is correct
18 Correct 515 ms 180344 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 180344 KB Output is correct
2 Correct 140 ms 180344 KB Output is correct
3 Correct 145 ms 180344 KB Output is correct
4 Correct 142 ms 180344 KB Output is correct
5 Correct 153 ms 180344 KB Output is correct
6 Correct 159 ms 180344 KB Output is correct
7 Correct 144 ms 180344 KB Output is correct
8 Correct 319 ms 185352 KB Output is correct
9 Correct 528 ms 185352 KB Output is correct
10 Correct 1095 ms 199740 KB Output is correct
11 Correct 498 ms 210616 KB Output is correct
12 Correct 535 ms 218964 KB Output is correct
13 Correct 127 ms 218964 KB Output is correct
14 Correct 374 ms 223436 KB Output is correct
15 Correct 207 ms 223436 KB Output is correct
16 Correct 1481 ms 234780 KB Output is correct
17 Correct 536 ms 243844 KB Output is correct
18 Correct 579 ms 252916 KB Output is correct
19 Runtime error 1097 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.
20 Halted 0 ms 0 KB -