oj.uz

Submission #927949

# Submission time Handle Problem Language Result Execution time Memory
927949 2024-02-15T14:30:06 Z TAhmed33 Wall (IOI14_wall) C++
100 / 100
 855 ms 57940 KB 
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
void chmin (int &x, int y) {
	x = min(x, y);
}
void chmax(int &x, int y) {
	x = max(x, y);
}
struct pp {
	int mx = 0, mn = 1e9;
};
struct SegmentTree {
	vector <pp> tree;
	void prop (int l, int r, int node) {
		if (l == r) return;
		chmin(tree[tl].mn, tree[node].mn);
		chmax(tree[tl].mn, tree[node].mx);
		chmax(tree[tl].mx, tree[node].mx);
		chmin(tree[tl].mx, tree[node].mn);
		chmin(tree[tr].mn, tree[node].mn);
		chmax(tree[tr].mn, tree[node].mx);
		chmax(tree[tr].mx, tree[node].mx);
		chmin(tree[tr].mx, tree[node].mn);
		tree[node].mn = 1e9; tree[node].mx = 0;
	}
	void update (int l, int r, int a, int b, int h, int t, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			if (t == 2) {
				chmin(tree[node].mn, h);
				chmin(tree[node].mx, h);
			}  else {
				chmax(tree[node].mn, h);
				chmax(tree[node].mx, h);
			}
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, h, t, tl);
		update(mid + 1, r, a, b, h, t, tr);
	}
	void dfs (int l, int r, int node) {
		prop(l, r, node);
		if (l == r) return;
		dfs(l, mid, tl);
		dfs(mid + 1, r, tr);
	}
	pp get (int l, int r, int a, int node) {
		if (l == r) {
			return tree[node];
		}
		if (mid < a) return get(mid + 1, r, a, tr);
		return get(l, mid, a, tl);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	SegmentTree cur; cur.tree.resize(2 * n);
	for (int i = 0; i < k; i++) {
		left[i]++; right[i]++;
	}
	for (int i = 0; i < k; i++) {
		cur.update(1, n, left[i], right[i], height[i], op[i], 1);
	}
	cur.dfs(1, n, 1);
	for (int i = 0; i < n; i++) {
		auto k = cur.get(1, n, i + 1, 1);
		finalHeight[i] = min(k.mn, k.mx);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 704 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 5 ms 700 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 101 ms 13908 KB Output is correct
3 Correct 167 ms 4688 KB Output is correct
4 Correct 484 ms 19688 KB Output is correct
5 Correct 299 ms 20276 KB Output is correct
6 Correct 287 ms 18696 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 6 ms 700 KB Output is correct
5 Correct 5 ms 700 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13908 KB Output is correct
9 Correct 200 ms 7804 KB Output is correct
10 Correct 479 ms 19728 KB Output is correct
11 Correct 305 ms 20308 KB Output is correct
12 Correct 285 ms 18660 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 105 ms 13908 KB Output is correct
15 Correct 28 ms 1784 KB Output is correct
16 Correct 511 ms 19692 KB Output is correct
17 Correct 301 ms 19284 KB Output is correct
18 Correct 298 ms 19028 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 5 ms 700 KB Output is correct
5 Correct 5 ms 700 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 103 ms 14032 KB Output is correct
9 Correct 178 ms 7760 KB Output is correct
10 Correct 483 ms 19700 KB Output is correct
11 Correct 304 ms 20328 KB Output is correct
12 Correct 296 ms 18700 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 105 ms 13904 KB Output is correct
15 Correct 35 ms 1624 KB Output is correct
16 Correct 488 ms 19684 KB Output is correct
17 Correct 298 ms 19028 KB Output is correct
18 Correct 290 ms 19116 KB Output is correct
19 Correct 806 ms 57940 KB Output is correct
20 Correct 797 ms 57684 KB Output is correct
21 Correct 793 ms 57824 KB Output is correct
22 Correct 784 ms 57596 KB Output is correct
23 Correct 788 ms 57580 KB Output is correct
24 Correct 807 ms 57692 KB Output is correct
25 Correct 855 ms 57688 KB Output is correct
26 Correct 799 ms 57692 KB Output is correct
27 Correct 787 ms 57604 KB Output is correct
28 Correct 814 ms 57688 KB Output is correct
29 Correct 769 ms 57940 KB Output is correct
30 Correct 807 ms 57940 KB Output is correct