제출 #1081038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081038		DarkMatter	벽 (IOI14_wall)	C++17	100 / 100	750 ms	120484 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree
{
	int n;
	vector<int>seg;
	vector<pair<int, int>>lazy;
	SegmentTree(int _n) {
		n = _n;
		seg.resize(4 * n + 5, 0);
		lazy.resize(4 * n + 5, { 1e9 + 7,-1 });
	}
	void push(int x, int lx, int rx) {
		if (lx == rx)
			return;
		if (lazy[x].first != 1e9) {
			seg[2 * x] = min(seg[2 * x], lazy[x].first);
			lazy[2 * x].first = min(lazy[2 * x].first, lazy[x].first);
			lazy[2 * x].second = min(lazy[2 * x].second, lazy[x].first);
			seg[2 * x + 1] = min(seg[2 * x + 1], lazy[x].first);
			lazy[2 * x + 1].first = min(lazy[2 * x + 1].first, lazy[x].first);
			lazy[2 * x + 1].second = min(lazy[2 * x + 1].second, lazy[x].first);
		}
		if (lazy[x].second != -1) {
			seg[2 * x] = max(seg[2 * x], lazy[x].second);
			lazy[2 * x].first = max(lazy[2 * x].first, lazy[x].second);
			lazy[2 * x].second = max(lazy[2 * x].second, lazy[x].second);
			seg[2 * x + 1] = max(seg[2 * x + 1], lazy[x].second);
			lazy[2 * x + 1].first = max(lazy[2 * x + 1].first, lazy[x].second);
			lazy[2 * x + 1].second = max(lazy[2 * x + 1].second, lazy[x].second);
		}
		lazy[x] = { 1e9,-1 };
	}
	void update(int x, int lx, int rx, int l, int r, int type, int v) {
		push(x, lx, rx);
		if (lx > rx || l > rx || lx > r)
			return;
		if (lx >= l && rx <= r) {
			if (type == 1)
				seg[x] = max(seg[x], v), lazy[x].first = max(lazy[x].first, v), lazy[x].second = max(lazy[x].second, v);
			else
				seg[x] = min(seg[x], v), lazy[x].first = min(lazy[x].first, v), lazy[x].second = min(lazy[x].second, v);
			push(x, lx, rx);
			return;
		}
		int mid = (lx + rx) / 2;
		update(2 * x, lx, mid, l, r, type, v);
		update(2 * x + 1, mid + 1, rx, l, r, type, v);
	}
	int get(int x, int lx, int rx, int i) {
		if (lx == rx)
			return seg[x];
		push(x, lx, rx);
		int mid = (lx + rx) / 2;
		if (i <= mid)
			return get(2 * x, lx, mid, i);
		else
			return get(2 * x + 1, mid + 1, rx, i);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	for (int i = 0; i < n; i++)
		finalHeight[i] = 0;
	SegmentTree seg(n);
	for (int i = 0; i < k; i++)
		seg.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
	for (int i = 0; i < n; i++)
		finalHeight[i] = seg.get(1, 0, n - 1, i);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39