Submission #211156

#	Time	Username	Problem	Language	Result	Execution time	Memory
211156		mode149256	Wall (IOI14_wall)	C++14	100 / 100	1213 ms	224880 KiB

wall

/*input

*/
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

struct node {
	int l, r;
	int low;
	int high;
	node *left = nullptr;
	node *right = nullptr;

	node(int a, int b): l(a), r(b) {
		low = 0;
		high = 0;
		if (l != r) {
			left = new node(l, (l + r) / 2);
			right = new node((l + r) / 2 + 1, r);
		}
	}

	inline void push() {
		if (l != r) {
			for (auto && chil : {left, right}) {
				chil->low = max(chil->low, low);
				chil->low = min(chil->low, high);

				chil->high = max(chil->high, low);
				chil->high = min(chil->high, high);
			}
		}
	}

	inline void fix() {
		if (l != r) {
			for (auto && chil : {left, right}) {
				low = min(chil->low, low);
				high = max(chil->high, high);
			}
		}
	}

	void addLow(int a, int b, int w) {
		push();
		if (r < a or b < l) return;
		else if (a <= l and r <= b) {
			low = max(low, w);
			high = max(high, low);
			return;
		} else {
			left->addLow(a, b, w);
			right->addLow(a, b, w);
		}
		fix();
	}

	void addHigh(int a, int b, int w) {
		push();
		if (r < a or b < l) return;
		else if (a <= l and r <= b) {
			high = min(high, w);
			low = min(high, low);
			return;
		} else {
			left->addHigh(a, b, w);
			right->addHigh(a, b, w);
		}
		fix();
	}

	void finish(int final[]) {
		push();
		if (l == r) {
			// printf("l = %d, r = %d, low = %d, high = %d\n", l, r, low, high);
			final[l] = low;
		} else {
			left->finish(final);
			right->finish(final);
		}
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	node medis(0, n - 1);
	for (int i = 0; i < k; ++i)
	{
		if (--op[i])
			medis.addHigh(left[i], right[i], height[i]);
		else
			medis.addLow(left[i], right[i], height[i]);
	}
	medis.finish(finalHeight);
}

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