oj.uz

Submission #593618

# Submission time Handle Problem Language Result Execution time Memory
593618 2022-07-11T12:41:39 Z Vanilla Wall (IOI14_wall) C++17
100 / 100
 600 ms 69584 KB 
#include <vector>
#include "wall.h"
using namespace std;
const int maxn = 2e6 + 1;
pair <int, int> sgt[maxn * 4];

void merge (int x, int mn2, int mx2) {
	sgt[x].first = min(sgt[x].first, mn2);
	sgt[x].second = max(min(mn2, sgt[x].second), mx2);
}

void propagate (int x) {
	merge(x * 2, sgt[x].first, sgt[x].second);
	merge(x * 2 + 1, sgt[x].first, sgt[x].second);
	sgt[x] = {1e6, 0};
}

void upd (int x, int l, int r, int il, int ir, int h, int op) {
	if (l > ir || r < il) return;
	if (il <= l && r <= ir) {
		if (op == 1) merge(x, 1e6, h);
		else merge(x, h, 0);
		return;
	}
	propagate(x);
	int mid = (l + r) / 2;
	upd(x * 2, l, mid, il, ir, h, op);
	upd(x * 2 + 1, mid + 1, r, il, ir, h, op);
}

void get (int x, int l, int r, int a[]){
	if (l > r) return;
	if (l == r) {
		a[l] = sgt[x].second;
		return;
	}
	propagate(x);
	int mid = (l + r) / 2;
	get(x * 2, l, mid, a);
	get(x * 2 + 1, mid + 1, r, a);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++){
		upd(1, 0, n-1, left[i], right[i], height[i], op[i]);
	}
	get(1, 0, n-1, finalHeight);
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 4 ms 816 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 130 ms 8280 KB Output is correct
3 Correct 160 ms 4372 KB Output is correct
4 Correct 346 ms 11424 KB Output is correct
5 Correct 236 ms 11852 KB Output is correct
6 Correct 219 ms 11808 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 4 ms 684 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 145 ms 8288 KB Output is correct
9 Correct 131 ms 4436 KB Output is correct
10 Correct 342 ms 11376 KB Output is correct
11 Correct 231 ms 11980 KB Output is correct
12 Correct 209 ms 11848 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 124 ms 8368 KB Output is correct
15 Correct 28 ms 1600 KB Output is correct
16 Correct 339 ms 11652 KB Output is correct
17 Correct 230 ms 11620 KB Output is correct
18 Correct 217 ms 11616 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 812 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 688 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 126 ms 8356 KB Output is correct
9 Correct 159 ms 4428 KB Output is correct
10 Correct 351 ms 11440 KB Output is correct
11 Correct 239 ms 11976 KB Output is correct
12 Correct 216 ms 11856 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 150 ms 8280 KB Output is correct
15 Correct 21 ms 1600 KB Output is correct
16 Correct 361 ms 11604 KB Output is correct
17 Correct 236 ms 11716 KB Output is correct
18 Correct 215 ms 11648 KB Output is correct
19 Correct 557 ms 59860 KB Output is correct
20 Correct 528 ms 66924 KB Output is correct
21 Correct 527 ms 69428 KB Output is correct
22 Correct 516 ms 66980 KB Output is correct
23 Correct 590 ms 67000 KB Output is correct
24 Correct 534 ms 66972 KB Output is correct
25 Correct 600 ms 67068 KB Output is correct
26 Correct 588 ms 69516 KB Output is correct
27 Correct 561 ms 69584 KB Output is correct
28 Correct 546 ms 67004 KB Output is correct
29 Correct 560 ms 66880 KB Output is correct
30 Correct 540 ms 66964 KB Output is correct