제출 #756584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756584		tcmmichaelb139	벽 (IOI14_wall)	C++17	100 / 100	1804 ms	135252 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39