oj.uz

Submission #812618

# Submission time Handle Problem Language Result Execution time Memory
812618 2023-08-07T09:35:34 Z Arturgo Wall (IOI14_wall) C++14
100 / 100
 1271 ms 69524 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

struct Label {
	int mini, maxi;

	Label(int _mini = 0, int _maxi = INFINI) {
		mini = _mini;
		maxi = _maxi;
	}
};

void append_label(Label& lbl, Label f) {
	lbl.mini = max(lbl.mini, f.mini);
	lbl.maxi = max(lbl.mini, lbl.maxi);
	lbl.maxi = min(lbl.maxi, f.maxi);
	lbl.mini = min(lbl.mini, lbl.maxi);
}

Label labels[(1 << 22)];

void push(int n) {
	if(n >= (1 << 21)) return;
	append_label(labels[2 * n], labels[n]);
	append_label(labels[2 * n + 1], labels[n]);
	labels[n] = Label();
}

void update(int l, int r, Label lbl, int n = 1, int ll = 0, int rr = (1 << 21)) {
	push(n);

	if(r <= ll || rr <= l) return;
	
	if(l <= ll && rr <= r) {
		append_label(labels[n], lbl);
		return;
	}

	int mm = (ll + rr) / 2;
	update(l, r, lbl, 2 * n, ll, mm);
	update(l, r, lbl, 2 * n + 1, mm, rr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for(int iOp = 0;iOp < k;iOp++) {
		int l = left[iOp], r = right[iOp] + 1, h = height[iOp];
		if(op[iOp] == 1) {
			// Adding phase
			update(l, r, {h, INFINI});
		}
		else {
			// Removing phase
			update(l, r, {0, h});
		}
	}

	for(int iPos = 0;iPos < n;iPos++) {
		update(iPos, iPos + 1, {});
		finalHeight[iPos] = labels[(1 << 21) + iPos].mini;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33108 KB Output is correct
2 Correct 17 ms 33260 KB Output is correct
3 Correct 16 ms 33092 KB Output is correct
4 Correct 23 ms 33332 KB Output is correct
5 Correct 24 ms 33340 KB Output is correct
6 Correct 22 ms 33364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33108 KB Output is correct
2 Correct 254 ms 46652 KB Output is correct
3 Correct 173 ms 40228 KB Output is correct
4 Correct 502 ms 51076 KB Output is correct
5 Correct 309 ms 52168 KB Output is correct
6 Correct 314 ms 50628 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 18 ms 33276 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 23 ms 33312 KB Output is correct
5 Correct 21 ms 33268 KB Output is correct
6 Correct 22 ms 33356 KB Output is correct
7 Correct 15 ms 33084 KB Output is correct
8 Correct 258 ms 46652 KB Output is correct
9 Correct 173 ms 40220 KB Output is correct
10 Correct 468 ms 51080 KB Output is correct
11 Correct 317 ms 52112 KB Output is correct
12 Correct 321 ms 50668 KB Output is correct
13 Correct 15 ms 33036 KB Output is correct
14 Correct 261 ms 46668 KB Output is correct
15 Correct 49 ms 34252 KB Output is correct
16 Correct 597 ms 51336 KB Output is correct
17 Correct 320 ms 50752 KB Output is correct
18 Correct 311 ms 50760 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33108 KB Output is correct
2 Correct 17 ms 33252 KB Output is correct
3 Correct 17 ms 33108 KB Output is correct
4 Correct 26 ms 33352 KB Output is correct
5 Correct 21 ms 33288 KB Output is correct
6 Correct 21 ms 33340 KB Output is correct
7 Correct 17 ms 33240 KB Output is correct
8 Correct 256 ms 46760 KB Output is correct
9 Correct 172 ms 40220 KB Output is correct
10 Correct 463 ms 51080 KB Output is correct
11 Correct 368 ms 52140 KB Output is correct
12 Correct 326 ms 50572 KB Output is correct
13 Correct 15 ms 33084 KB Output is correct
14 Correct 267 ms 46664 KB Output is correct
15 Correct 49 ms 34296 KB Output is correct
16 Correct 578 ms 51336 KB Output is correct
17 Correct 313 ms 50756 KB Output is correct
18 Correct 318 ms 50748 KB Output is correct
19 Correct 1106 ms 69440 KB Output is correct
20 Correct 1086 ms 67000 KB Output is correct
21 Correct 1214 ms 69524 KB Output is correct
22 Correct 1120 ms 66908 KB Output is correct
23 Correct 1096 ms 66968 KB Output is correct
24 Correct 1097 ms 66992 KB Output is correct
25 Correct 1134 ms 66996 KB Output is correct
26 Correct 1091 ms 69440 KB Output is correct
27 Correct 1105 ms 69508 KB Output is correct
28 Correct 1213 ms 66976 KB Output is correct
29 Correct 1271 ms 66908 KB Output is correct
30 Correct 1093 ms 67020 KB Output is correct