oj.uz

Submission #65313

# Submission time Handle Problem Language Result Execution time Memory
65313 2018-08-07T11:23:54 Z gnoor Wall (IOI14_wall) C++17
32 / 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) {
		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 124 ms 156920 KB Output is correct
2 Correct 130 ms 157044 KB Output is correct
3 Correct 145 ms 157060 KB Output is correct
4 Correct 156 ms 157412 KB Output is correct
5 Correct 129 ms 157492 KB Output is correct
6 Correct 129 ms 157560 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 157560 KB Output is correct
2 Correct 356 ms 171132 KB Output is correct
3 Correct 478 ms 171132 KB Output is correct
4 Correct 1107 ms 185692 KB Output is correct
5 Correct 497 ms 196448 KB Output is correct
6 Correct 503 ms 204960 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 204960 KB Output is correct
2 Correct 138 ms 204960 KB Output is correct
3 Correct 142 ms 204960 KB Output is correct
4 Correct 147 ms 204960 KB Output is correct
5 Correct 139 ms 204960 KB Output is correct
6 Correct 129 ms 204960 KB Output is correct
7 Correct 139 ms 204960 KB Output is correct
8 Correct 396 ms 209632 KB Output is correct
9 Correct 548 ms 209632 KB Output is correct
10 Correct 1233 ms 224200 KB Output is correct
11 Correct 436 ms 234760 KB Output is correct
12 Correct 473 ms 243504 KB Output is correct
13 Correct 124 ms 243504 KB Output is correct
14 Correct 331 ms 247648 KB Output is correct
15 Correct 222 ms 247648 KB Output is correct
16 Correct 1390 ms 259148 KB Output is correct
17 Runtime error 493 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.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 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.
2 Halted 0 ms 0 KB -