oj.uz

Submission #779763

# Submission time Handle Problem Language Result Execution time Memory
779763 2023-07-11T19:06:37 Z zsombor Wall (IOI14_wall) C++17
100 / 100
 754 ms 142328 KB 
#include <iostream>
#include <vector>
//#include "wall.h"
using namespace std;

struct node {
	int L, M, R, MN, MX;
	node() { MN = 0; MX = 1e5; }
};

vector <node> sgt(5e6, node());
vector <int> ans(2e6);

void build_sgt(int x, int l, int r) {
	sgt[x].L = l;
	sgt[x].M = (l + r) / 2;
	sgt[x].R = r;
	if (r - l == 1) { sgt[x].MX = 0; return; }
	build_sgt(2 * x, l, (l + r) / 2);
	build_sgt(2 * x + 1, (l + r) / 2, r);
}

void update_node(int x, int mn, int mx) {
	if (mx < sgt[x].MN) { sgt[x].MN = sgt[x].MX = mx; return; }
	if (mn > sgt[x].MX) { sgt[x].MN = sgt[x].MX = mn; return; }
	sgt[x].MN = max(sgt[x].MN, mn);
	sgt[x].MX = min(sgt[x].MX, mx);
}

void push_down(int x) {
	if (sgt[x].R - sgt[x].L == 1) return;
	update_node(2 * x, sgt[x].MN, sgt[x].MX);
	update_node(2 * x + 1, sgt[x].MN, sgt[x].MX);
	sgt[x].MN = 0;
	sgt[x].MX = 1e5;
}

void update(int x, int l, int r, int mn, int mx) {
	push_down(x);
	if (r <= sgt[x].L || sgt[x].R <= l) return;
	if (l <= sgt[x].L && sgt[x].R <= r) { update_node(x, mn, mx); return; }
	update(2 * x, l, r, mn, mx);
	update(2 * x + 1, l, r, mn, mx);
}

void get_ans(int x) {
	if (sgt[x].R - sgt[x].L == 1) { ans[sgt[x].L] = sgt[x].MN; return; }
	push_down(x);
	get_ans(2 * x);
	get_ans(2 * x + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	build_sgt(1, 0, n);
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) update(1, left[i], right[i] + 1, height[i], 1e5);
		else update(1, left[i], right[i] + 1, 0, height[i]);
	}
	get_ans(1);
	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 51 ms 105880 KB Output is correct
2 Correct 41 ms 105976 KB Output is correct
3 Correct 42 ms 105912 KB Output is correct
4 Correct 48 ms 106104 KB Output is correct
5 Correct 44 ms 106144 KB Output is correct
6 Correct 45 ms 106096 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 105932 KB Output is correct
2 Correct 142 ms 113876 KB Output is correct
3 Correct 195 ms 109388 KB Output is correct
4 Correct 507 ms 123928 KB Output is correct
5 Correct 306 ms 124984 KB Output is correct
6 Correct 311 ms 123436 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 105936 KB Output is correct
2 Correct 41 ms 105948 KB Output is correct
3 Correct 42 ms 105984 KB Output is correct
4 Correct 46 ms 106108 KB Output is correct
5 Correct 45 ms 106032 KB Output is correct
6 Correct 44 ms 106088 KB Output is correct
7 Correct 40 ms 105880 KB Output is correct
8 Correct 138 ms 113752 KB Output is correct
9 Correct 193 ms 109312 KB Output is correct
10 Correct 498 ms 123940 KB Output is correct
11 Correct 304 ms 125064 KB Output is correct
12 Correct 317 ms 123428 KB Output is correct
13 Correct 43 ms 105932 KB Output is correct
14 Correct 150 ms 119544 KB Output is correct
15 Correct 92 ms 107156 KB Output is correct
16 Correct 717 ms 124156 KB Output is correct
17 Correct 339 ms 123612 KB Output is correct
18 Correct 348 ms 123604 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 105932 KB Output is correct
2 Correct 53 ms 105976 KB Output is correct
3 Correct 45 ms 105996 KB Output is correct
4 Correct 49 ms 106104 KB Output is correct
5 Correct 47 ms 106056 KB Output is correct
6 Correct 45 ms 106024 KB Output is correct
7 Correct 42 ms 105936 KB Output is correct
8 Correct 140 ms 113740 KB Output is correct
9 Correct 200 ms 109300 KB Output is correct
10 Correct 518 ms 123932 KB Output is correct
11 Correct 311 ms 124988 KB Output is correct
12 Correct 319 ms 123364 KB Output is correct
13 Correct 49 ms 105932 KB Output is correct
14 Correct 148 ms 119492 KB Output is correct
15 Correct 77 ms 107068 KB Output is correct
16 Correct 724 ms 124184 KB Output is correct
17 Correct 372 ms 123624 KB Output is correct
18 Correct 334 ms 123604 KB Output is correct
19 Correct 725 ms 142292 KB Output is correct
20 Correct 724 ms 139796 KB Output is correct
21 Correct 733 ms 142328 KB Output is correct
22 Correct 713 ms 139848 KB Output is correct
23 Correct 743 ms 139912 KB Output is correct
24 Correct 712 ms 139856 KB Output is correct
25 Correct 727 ms 139752 KB Output is correct
26 Correct 741 ms 142300 KB Output is correct
27 Correct 727 ms 142296 KB Output is correct
28 Correct 754 ms 139732 KB Output is correct
29 Correct 720 ms 139912 KB Output is correct
30 Correct 741 ms 139768 KB Output is correct