Submission #763111

#	Time	Username	Problem	Language	Result	Execution time	Memory
763111		SanguineChameleon	Wall (IOI14_wall)	C++17	100 / 100	569 ms	69528 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 20;
const int maxn = 2e6 + 20;
pair<int, int> tree[maxn * 4];

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = make_pair(0, 0);
		return;
	}
	tree[id] = make_pair(-inf, inf);
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
}

void update(int id, int lt, int rt) {
	if (tree[id].second < lt) {
		tree[id] = make_pair(lt, lt);
	}
	else if (tree[id].first > rt) {
		tree[id] = make_pair(rt, rt);
	}
	else {
		tree[id] = make_pair(max(lt, tree[id].first), min(rt, tree[id].second));
	}
}

void push(int id) {
	update(id * 2, tree[id].first, tree[id].second);
	update(id * 2 + 1, tree[id].first, tree[id].second);
	tree[id] = make_pair(-inf, inf);
}

void update(int id, int lt, int rt, int ql, int qr, int op, int h) {
	if (lt == ql && rt == qr) {
		if (op == 1) {
			update(id, h, inf);
		}
		else {
			update(id, -inf, h);
		}
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr, op, h);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr, op, h);
	}
	else {
		update(id * 2, lt, mt, ql, mt, op, h);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr, op, h);
	}
}

int *finalHeight;

void push_all(int id, int lt, int rt) {
	if (lt == rt) {
		finalHeight[lt - 1] = tree[id].first;
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	push_all(id * 2, lt, mt);
	push_all(id * 2 + 1, mt + 1, rt);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int _finalHeight[]) {
	finalHeight = _finalHeight;
	build(1, 1, n);
	for (int i = 0; i < q; i++) {
		update(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]);
	}
	push_all(1, 1, n);
}

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