Submission #655067

#	Time	Username	Problem	Language	Result	Execution time	Memory
655067		thiago_bastos	Wall (IOI14_wall)	C++17	100 / 100	1866 ms	80184 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
 
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;	

const int N = 1 << 22;

struct Item {
	int type;
	int x, y;
};

Item lazy[N];
bool marked[N];

int F(Item i, int x) {
	if(i.type == 0) return max(i.x, min(i.y, x));
	return min(i.x, max(i.y, x));
}

Item A[2][2][4][4][4][4];
bool vis[2][2][4][4][4][4];

Item merge(Item a, Item b) {
	int p[4] = {a.x, a.y, b.x, b.y};

	sort(p, p + 4);

	auto [_, ax, ay] = a;
	auto [__, bx, by] = b;

	ax = lower_bound(p, p + 4, ax) - p;
	ay = lower_bound(p, p + 4, ay) - p;
	bx = lower_bound(p, p + 4, bx) - p;
	by = lower_bound(p, p + 4, by) - p;

	if(vis[a.type][b.type][ax][ay][bx][by]) {
		auto k = A[a.type][b.type][ax][ay][bx][by];
		return {k.type, p[k.x], p[k.y]};
	}

	for(int t : {0, 1}) {
		for(int i = 0; i < 4; ++i) {
		for(int j = 0; j < 4; ++j) {
				bool ok = true;
				for(int x : p) ok = ok && F(a, F(b, x)) == F({t, p[i], p[j]}, x);
				if(ok) {
					vis[a.type][b.type][ax][ay][bx][by] = true;
					A[a.type][b.type][ax][ay][bx][by] = {t, i, j};
					return {t, p[i], p[j]};
				}
			}
		}
	}

	return {0,0,0};
}

void build(int l, int r, int k = 1) {
	lazy[k] = {0, 0, INF};
	if(l != r) {
		build(l, (l + r) / 2, 2 * k);
		build((l + r) / 2 + 1, r, 2 * k + 1);
	}
}

void push(int k) {
	if(!marked[k]) return;
	for(int i : {2 * k, 2 * k + 1}) {
		marked[i] = true;
		lazy[i] = merge(lazy[k], lazy[i]);
	}
	lazy[k] = {0, 0, INF};
	marked[k] = false;
}

void upd(int l, int r, Item x, int lo, int hi, int k = 1) {
	if(l > r || lo > hi || r < lo || hi < l) return;
	else if(lo >= l && hi <= r) {
		lazy[k] = merge(x, lazy[k]);
		marked[k] = true;
	} else {
		int m = (lo + hi) / 2;
		push(k);
		upd(l, r, x, lo, m, 2 * k);
		upd(l, r, x, m + 1, hi, 2 * k + 1);
	}
}

int query(int i, int lo, int hi, int k = 1) {
	if(lo == hi) return F(lazy[k], 0);
	int m = (lo + hi) / 2;
	push(k);
	return i <= m ? query(i, lo, m, 2 * k) : query(i, m + 1, hi, 2 * k + 1);
}

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

	for(int i = 0; i < k; ++i) {
		Item v;

		if(op[i] == 1) {
			v.type = 0;
			v.x = height[i];
			v.y = INF;
		} else {
			v.type = 1;
			v.x = height[i];
			v.y = 0;
		}
		
		upd(left[i], right[i], v, 0, n - 1);
	}

	for(int i = 0; i < n; ++i)
		finalHeight[i] = query(i, 0, n - 1);

	return;
}

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