Submission #48249

#	Time	Username	Problem	Language	Result	Execution time	Memory
48249		cheater2k	Wall (IOI14_wall)	C++17	100 / 100	1158 ms	262144 KiB

wall

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

typedef pair<int,int> ii;

const int N = 2000005;

// SEGMENT TREE
int mn[N << 2];
int mx[N << 2];
int lz[N << 2];
int segpos[N];
#define mid ((l + r) >> 1)

void build(int v, int l, int r) {
	mn[v] = 0;
	mx[v] = 0;
	lz[v] = -1;
	if (l == r) {
		segpos[l] = v;
		return;
	}
	build(v << 1, l, mid);
	build(v << 1 | 1, mid + 1, r);
}

void push(int v, int l, int r) {
	if (lz[v] == -1) return;
	if (l < r) lz[v << 1] = lz[v], lz[v << 1 | 1] = lz[v];
	mn[v] = mx[v] = lz[v];
	lz[v] = -1;
}

void upd(int v, int l, int r, int L, int R, int val) {
	push(v, l, r);
	if (R < l || L > r) return;
	if (L <= l && r <= R) {
		lz[v] = val; push(v, l, r); return;
	}
	upd(v << 1, l, mid, L, R, val);
	upd(v << 1 | 1, mid + 1, r, L, R, val);
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
}

int find_smaller(int v, int l, int r, int leftmost, int h) {
	// find the smallest i >= leftmost s.t. a[i] < h
	push(v, l, r);
	if (r < leftmost) return N;
	if (l >= leftmost) {
		if (l == r) {
			if (mn[v] < h) return l;
			else return N;
		}
		if (mn[v] >= h) return N;
	}

	int gl = find_smaller(v << 1, l, mid, leftmost, h);
	if (gl != N) return gl;
	else return find_smaller(v << 1 | 1, mid + 1, r, leftmost, h);
}

int find_greater(int v, int l, int r, int leftmost, int h) {
	// find the smallest i >= leftmost s.t. a[i] > h
	push(v, l, r);
	if (r < leftmost) return N;
	if (l >= leftmost) {
		if (l == r) {
			if (mx[v] > h) return l;
			else return N;
		}
		if (mx[v] <= h) return N;
	}

	int gl = find_greater(v << 1, l, mid, leftmost, h);
	if (gl != N) return gl;
	else return find_greater(v << 1 | 1, mid + 1, r, leftmost, h);
}

void final(int v, int l, int r) {
	push(v, l, r);
	if (l == r) return;
	final(v << 1, l, mid);
	final(v << 1 | 1, mid + 1, r);
}

#undef mid

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(1, 0, n - 1);

	for (int i = 0; i < k; ++i) {
		if (op[i] == 1) { // add
			int pos = left[i];
			while(pos <= right[i]) {
				int posl = find_smaller(1, 0, n - 1, pos, height[i]);
				if (posl == N) break;
				int posr = find_greater(1, 0, n - 1, posl, height[i]);
				posr = min(posr - 1, right[i]);

				upd(1, 0, n - 1, posl, posr, height[i]);
				pos = posr + 1;
			}
		} else { // remove
			int pos = left[i];
			while(pos <= right[i]) {
				int posl = find_greater(1, 0, n - 1, pos, height[i]);
				if (posl == N) break;
				int posr = find_smaller(1, 0, n - 1, posl, height[i]);
				posr = min(posr - 1, right[i]);

				upd(1, 0, n - 1, posl, posr, height[i]);
				pos = posr + 1;
			}
		}
	}

	final(1, 0, n - 1);
	for (int i = 0; i < n; ++i) {
		finalHeight[i] = mn[segpos[i]];
	}
}

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