Submission #139652

#	Time	Username	Problem	Language	Result	Execution time	Memory
139652		dcordb	Wall (IOI14_wall)	C++11	100 / 100	2651 ms	126844 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
const int
	MAX = 2e6 + 5,
	INF = 1e6;
int lazy[4 * MAX][5];
int a[MAX];

int reduce(const int &a, const int &b, bool &ok) {
	int x = abs(a);
	int y = abs(b);
 
	if(a < 0 && b < 0)
		return (x <= y) ? a : b;
 
	if(a >= 0 && b >= 0)
		return (x <= y) ? b : a;
 
	ok = false;
	return 0;
}
 
void transform(int &a, int &b) {
	int x = abs(a);
	int y = abs(b);
 
	if(a < 0 && b >= 0) {
		if(x <= y) {
			a = INF;
			b *= -1;
		}
 
		else swap(a, b);
	}
 
	else {
		assert(b < 0);
 
		if(x <= y)
			swap(a, b);
 
		else {
			a = -1;
			b *= -1;
		}
	}
}

void reduce(int a, int b) {
	for(int i = 1; i <= lazy[b][0]; i++) {
		int p = ++lazy[a][0];
		lazy[a][p] = lazy[b][i];
	}

	assert(lazy[a][0] <= 4);

	int s[lazy[a][0]]; int k = 0;

	for(int i = 1; i <= lazy[a][0]; i++) {
		int o = lazy[a][i];

		if(k == 0) {
			s[k++] = o;
			continue;
		}

		int x = s[k - 1];
		k--;

		bool ok = true;
		int r = reduce(x, o, ok);

		if(ok)
			s[k++] = r;

		else {
			if(k == 0) {
				s[k++] = x;
				s[k++] = o;
			}

			else {
				int y = s[k - 1];
				k--;

				transform(y, x);

				s[k++] = y;

				ok = true;
				r = reduce(x, o, ok);
				assert(ok);

				s[k++] = r;
			}
		}
	}

	lazy[a][0] = k;
	for(int i = 0; i < k; i++)
		lazy[a][i + 1] = s[i];
}
 
void build(int x, int st, int nd) {
	lazy[x][++lazy[x][0]] = 0;
 
	if(st == nd) return;
 
	int mid = (st + nd) >> 1;
	build(2 * x, st, mid);
	build(2 * x + 1, mid + 1, nd);
}
 
void prop(int x, int st, int nd) {
	if(lazy[x][0] == 1 && lazy[x][1] == 0)
		return;

	if(st == nd) {
		for(int i = 1; i <= lazy[x][0]; i++) {
			int o = lazy[x][i];

			if(o >= 0)
				a[st] = max(a[st], o);
 
			else a[st] = min(a[st], -o);
		}
	}
 
	else {
		reduce(2 * x, x);
		reduce(2 * x + 1, x);
	}
 	
 	lazy[x][0] = 0;
 	lazy[x][++lazy[x][0]] = 0;
}
 
void upd(int x, int st, int nd, int a, int b, const int &o) {
	prop(x, st, nd);
 
	if(st > b || nd < a)
		return;
 
	if(st >= a && nd <= b) {
		lazy[x][0] = 0;
 		lazy[x][++lazy[x][0]] = o;

		prop(x, st, nd);
		return;
	}
 
	int mid = (st + nd) >> 1;
	upd(2 * x, st, mid, a, b, o);
	upd(2 * x + 1, mid + 1, nd, a, b, o);
}
 
void buildWall(int n, int m, int operation[], int l[], int r[], int h[], int ans[]) {
	build(1, 0, n - 1);
 
	for(int i = 0; i < m; i++) {
		int height = h[i] + 1;
 
		if(operation[i] == 1)
			upd(1, 0, n - 1, l[i], r[i], height);
 
		else upd(1, 0, n - 1, l[i], r[i], -height);
	}
 
	for(int i = 0; i < n; i++) {
		upd(1, 0, n - 1, i, i, 0);
		ans[i] = max(0, a[i] - 1);
	}
}

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