oj.uz

Submission #756584

# Submission time Handle Problem Language Result Execution time Memory
756584 2023-06-12T00:54:11 Z tcmmichaelb139 Wall (IOI14_wall) C++17
100 / 100
 1804 ms 135252 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

struct Node {
	long long val;
	long long gt;
	long long lt;
};

template <class T, int N>
struct LazySeg {
	static_assert(__builtin_popcount(N) == 1);
	const T ID = {0, 0, (long long)1e18};
	long long cmb(long long a, long long b) { return a + b; }
	T seg[2 * N];
	LazySeg() {
		for (int i = 0; i < 2 * N; i++)
			seg[i] = ID;
	}
	void push(int p, int L, int R) {
		seg[p].val = max(seg[p].val, seg[p].gt);
		seg[p].val = min(seg[p].val, seg[p].lt);
		if (L != R) {
			if (seg[p].lt < seg[2 * p].gt) {
				seg[2 * p].gt = seg[2 * p].lt = seg[p].lt;
			} else if (seg[p].gt > seg[2 * p].lt) {
				seg[2 * p].gt = seg[2 * p].lt = seg[p].gt;
			} else {
				seg[2 * p].gt = max(seg[2 * p].gt, seg[p].gt);
				seg[2 * p].lt = min(seg[2 * p].lt, seg[p].lt);
			}
			if (seg[p].lt < seg[2 * p + 1].gt) {
				seg[2 * p + 1].gt = seg[2 * p + 1].lt = seg[p].lt;
			} else if (seg[p].gt > seg[2 * p + 1].lt) {
				seg[2 * p + 1].gt = seg[2 * p + 1].lt = seg[p].gt;
			} else {
				seg[2 * p + 1].gt = max(seg[2 * p + 1].gt, seg[p].gt);
				seg[2 * p + 1].lt = min(seg[2 * p + 1].lt, seg[p].lt);
			}
		}
		seg[p].gt = 0;
		seg[p].lt = 1e18;
	}
	void pull(int p) { seg[p].val = cmb(seg[2 * p].val, seg[2 * p + 1].val); }
	void upd(int lo, int hi, pair<int, long long> inc, int p = 1, int L = 0, int R = N - 1) {
		push(p, L, R);
		if (lo > R || L > hi) return;
		if (lo <= L && R <= hi) {
			if (inc.first == 1) {
				seg[p].gt = inc.second;
			} else {
				seg[p].lt = inc.second;
			}
			push(p, L, R);
			return;
		}
		int M = (L + R) / 2;
		upd(lo, hi, inc, 2 * p, L, M);
		upd(lo, hi, inc, 2 * p + 1, M + 1, R);
		pull(p);
	}
	long long query(int lo, int hi, int p = 1, int L = 0, int R = N - 1) {
		push(p, L, R);
		if (lo > R || L > hi) return ID.val;
		if (lo <= L && R <= hi) return seg[p].val;
		int M = (L + R) / 2;
		return cmb(query(lo, hi, 2 * p, L, M), query(lo, hi, 2 * p + 1, M + 1, R));
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	LazySeg<Node, 1 << 21> seg;

	for (int i = 0; i < k; i++) {
		seg.upd(left[i], right[i], {op[i], height[i]});
	}

	for (int i = 0; i < n; i++) {
		finalHeight[i] = seg.query(i, i);
	}

	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98760 KB Output is correct
2 Correct 53 ms 98928 KB Output is correct
3 Correct 54 ms 98772 KB Output is correct
4 Correct 72 ms 99028 KB Output is correct
5 Correct 64 ms 98972 KB Output is correct
6 Correct 60 ms 98956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98684 KB Output is correct
2 Correct 406 ms 112440 KB Output is correct
3 Correct 324 ms 105884 KB Output is correct
4 Correct 750 ms 116756 KB Output is correct
5 Correct 495 ms 117764 KB Output is correct
6 Correct 508 ms 116236 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98664 KB Output is correct
2 Correct 54 ms 98992 KB Output is correct
3 Correct 60 ms 98836 KB Output is correct
4 Correct 64 ms 99016 KB Output is correct
5 Correct 65 ms 98980 KB Output is correct
6 Correct 60 ms 98928 KB Output is correct
7 Correct 48 ms 98680 KB Output is correct
8 Correct 427 ms 112428 KB Output is correct
9 Correct 288 ms 105876 KB Output is correct
10 Correct 770 ms 116780 KB Output is correct
11 Correct 526 ms 117804 KB Output is correct
12 Correct 498 ms 116240 KB Output is correct
13 Correct 57 ms 98772 KB Output is correct
14 Correct 400 ms 112432 KB Output is correct
15 Correct 102 ms 99956 KB Output is correct
16 Correct 860 ms 117056 KB Output is correct
17 Correct 509 ms 116456 KB Output is correct
18 Correct 507 ms 116424 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98760 KB Output is correct
2 Correct 51 ms 98856 KB Output is correct
3 Correct 52 ms 98816 KB Output is correct
4 Correct 60 ms 98992 KB Output is correct
5 Correct 59 ms 98972 KB Output is correct
6 Correct 61 ms 98968 KB Output is correct
7 Correct 50 ms 98720 KB Output is correct
8 Correct 396 ms 112324 KB Output is correct
9 Correct 317 ms 105876 KB Output is correct
10 Correct 768 ms 116804 KB Output is correct
11 Correct 518 ms 117824 KB Output is correct
12 Correct 557 ms 116340 KB Output is correct
13 Correct 49 ms 98764 KB Output is correct
14 Correct 395 ms 112436 KB Output is correct
15 Correct 99 ms 99928 KB Output is correct
16 Correct 899 ms 116996 KB Output is correct
17 Correct 506 ms 116564 KB Output is correct
18 Correct 530 ms 116436 KB Output is correct
19 Correct 1802 ms 135216 KB Output is correct
20 Correct 1757 ms 132680 KB Output is correct
21 Correct 1766 ms 135252 KB Output is correct
22 Correct 1753 ms 132644 KB Output is correct
23 Correct 1804 ms 132800 KB Output is correct
24 Correct 1734 ms 132864 KB Output is correct
25 Correct 1769 ms 132924 KB Output is correct
26 Correct 1769 ms 135104 KB Output is correct
27 Correct 1766 ms 135216 KB Output is correct
28 Correct 1757 ms 132712 KB Output is correct
29 Correct 1766 ms 132728 KB Output is correct
30 Correct 1756 ms 132664 KB Output is correct