Submission #1257779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257779		ciao_gio	Wall (IOI14_wall)	C++20	100 / 100	430 ms	49780 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

struct Segment {
	struct Node {
		int mn = 0;
		int mx = INF;

		Node() : mn(0), mx(INF) {}

		void add(int h) {
			mn = max(mn, h);
			mx = max(mx, mn);
		}

		void remove(int h) {
			mx = min(mx, h);
			mn = min(mn, mx);
		}
	};

	int n;
	vector<Node> t;

	Segment(int _n) {
		for (n = 1; n < _n; n *= 2)
			;
		t.resize(2 * n);
	}

	void prop(int i) {
		t[2 * i].add(t[i].mn);
		t[2 * i].remove(t[i].mx);
		t[2 * i + 1].add(t[i].mn);
		t[2 * i + 1].remove(t[i].mx);
		t[i] = Node();
	}

	void update(int i, int a, int b, int l, int r, int h, bool flag) {
		if (b <= l || r <= a)
			return;
		if (l <= a && b <= r) {
			if (flag)
				t[i].add(h);
			else
				t[i].remove(h);
			return;
		}

		prop(i);

		int m = (a + b) / 2;
		update(2 * i, a, m, l, r, h, flag);
		update(2 * i + 1, m, b, l, r, h, flag);
	}

	void update(int l, int r, int h, bool flag = true) {
		update(1, 0, n, l, r, h, flag);
	}

	int query(int p) {
		int ans = 0;
		for (p += n; p > 0; p >>= 1) {
			ans = max(ans, t[p].mn);
			ans = min(ans, t[p].mx);
		}
		return ans;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	Segment T(n);

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

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

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