Submission #58062

#	Time	Username	Problem	Language	Result	Execution time	Memory
58062		aome	Wall (IOI14_wall)	C++17	100 / 100	1530 ms	226784 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 2000005;

struct Node {
	int min, max;

	Node() { min = 0, max = 1e9; }

	Node(int min, int max) : min(min), max(max) {}
};

struct SegmentTree {

	Node T[N << 2];

	#define mid ((l + r) >> 1)

	void upd(int i, int l, int r, int p, Node x) {
		if (l == r) {
			T[i] = x; return;
		}
		if (mid >= p) upd(i << 1, l, mid, p, x);
		else upd(i << 1 | 1, mid + 1, r, p, x);
		T[i].min = max(T[i << 1].min, T[i << 1 | 1].min);
		T[i].max = min(T[i << 1].max, T[i << 1 | 1].max);
	}

	int get1(int i, int l, int r, Node x) {
		if (l == r) return l;
		Node y;
		y.min = max(x.min, T[i << 1 | 1].min);
		y.max = min(x.max, T[i << 1 | 1].max);
		if (y.min > y.max) {
			return get1(i << 1 | 1, mid + 1, r, x);
		}
		return get1(i << 1, l, mid, y);
	}

	void get2(int i, int l, int r, int L, int R, Node& x) {
		if (l > R || L > r) return;
		if (L <= l && r <= R) {
			x.min = max(x.min, T[i].min);
			x.max = min(x.max, T[i].max);
			return;
		}
		get2(i << 1, l, mid, L, R, x);
		get2(i << 1 | 1, mid + 1, r, L, R, x);
	}

	#undef mid
} IT;

struct Event {
	int v, p, x, y, t;

	bool operator < (const Event& rhs) const {
		return v < rhs.v;
	}
};

void buildWall(int n, int m, int op[], int left[], int right[], int height[], int finalHeight[]) {
	vector<Event> events;
	for (int i = 0; i < m; ++i) {
		events.push_back({left[i], i, height[i], op[i], 0});
		events.push_back({right[i] + 1, i, height[i], op[i], 1});
	}
	sort(events.begin(), events.end());
	int ptr = 0;
	for (int i = 0; i < n; ++i) {
		// cout << "#at " << i << '\n';
		while (ptr < 2 * m && events[ptr].v <= i) {
			if (events[ptr].t == 0) {
				if (events[ptr].y == 2) {
					// cout << "#add2 " << events[ptr].p << '\n';
					IT.upd(1, 0, m - 1, events[ptr].p, Node(0, events[ptr].x));
				}
				else {
					// cout << "#add1 " << events[ptr].p << '\n';
					IT.upd(1, 0, m - 1, events[ptr].p, Node(events[ptr].x, 1e9));
				}
			}
			else {
				// cout << "#del " << events[ptr].p << '\n';
				IT.upd(1, 0, m - 1, events[ptr].p, Node());
			}
			++ptr;
		}
		int v, L, R;
		if (IT.T[1].min <= IT.T[1].max) {
			L = IT.T[1].min, R = IT.T[1].max, v = 0;
		}
		else {
			int p = IT.get1(1, 0, m - 1, Node());
			// cout << "#p " << p << '\n';
			v = height[p];
			Node x = Node();
			IT.get2(1, 0, m - 1, p + 1, m - 1, x);
			L = x.min, R = x.max;
		}
		// cout << v << ' ' << L << ' ' << R << '\n';
		if (v < L) finalHeight[i] = L;
		else if (v > R) finalHeight[i] = R;
		else finalHeight[i] = v;
	}
}

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