Submission #337893

#	Time	Username	Problem	Language	Result	Execution time	Memory
337893		Azimjon	Wall (IOI14_wall)	C++17	61 / 100	841 ms	48236 KiB

wall

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

using namespace std;

const int INF = 1e9;
const int N = 2e6 + 10;

int ka[N], ki[N];
bool ish[N];
int n;

void minim(int, int, int, int, int, int);
void maxim(int, int, int, int, int, int);

void init() {
	for (int i = 0; i < N; i++) {
		ka[i] = 0;
		ki[i] = INF;
	}
}

void minim(int v, int l, int r, int tl, int tr, int h) {
	if (tr < l || r < tl) return;

	if (tl <= l && r <= tr) {
		ki[v] = min(ki[v], h);
		ka[v] = min(ka[v], ki[v]);
		ish[v] = 1;

		return;
	}

	int m = (l + r) / 2;
	if (ish[v]) {
		ish[v] = 0;
		ish[2 * v] = ish[2 * v + 1] = 1;

		maxim(2 * v, l, m, l, m, ka[v]);
		minim(2 * v, l, m, l, m, ki[v]);
		maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
		minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
		ka[v] = 0;
		ki[v] = INF;
	}
	minim(2 * v, l, m, tl, tr, h);
	minim(2 * v + 1, m + 1, r, tl, tr, h);
}

void maxim(int v, int l, int r, int tl, int tr, int h) {
	if (tr < l || r < tl) return;

	if (tl <= l && r <= tr) {
		ka[v] = max(ka[v], h);
		ki[v] = max(ki[v], ka[v]);
		ish[v] = 1;
		return;
	}
	int m = (l + r) / 2;
	if (ish[v]) {
		ish[v] = 0;

		ish[2 * v] = ish[2 * v + 1] = 1;
		minim(2 * v, l, m, l, m, ki[v]);
		maxim(2 * v, l, m, l, m, ka[v]);
		minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
		maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
		ka[v] = 0;
		ki[v] = INF;
	}
	maxim(2 * v, l, m, tl, tr, h);
	maxim(2 * v + 1, m + 1, r, tl, tr, h);
}

int get(int v, int l, int r, int x) {
	if (l == r) {
		return ka[v];
	}

	int m = (l + r) / 2;
	if (x <= m)
		return get(2 * v, l, m, x);
	else
		return get(2 * v + 1, m + 1, r, x);
}

void buildWall(int nn, int k, int op[], int left[], int right[], int height[],
			   int finalHeight[]) {
	n = nn;
	init();

	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			maxim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
		} else {
			minim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
		}
	}

	for (int i = 1; i <= n; i++) {
		minim(1, 1, n, i, i, INF);
		// maxim(1, 1, n, i, i, 0);
		finalHeight[i - 1] = get(1, 1, n, i);
	}

	return;
}

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