제출 #927949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927949		TAhmed33	벽 (IOI14_wall)	C++98	100 / 100	855 ms	57940 KiB

wall

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