Submission #1007145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007145		pawned	Wall (IOI14_wall)	C++17	100 / 100	733 ms	54520 KiB

wall

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "wall.h"

ii combine(ii p1, ii p2) {	// apply p1 on p2 (p1 is newer)
	// (a, b) [later] done on (c, d)
	// becomes (max(a, c), min(b, d))
	// if min(b, d) > max(a, c), know that [a, b] and [c, d] are disjoint
	// if b < d, then becomes (b, b); otherwise becomes (c, c)
	ii res = {max(p1.fi, p2.fi), min(p1.se, p2.se)};
	if (res.fi > res.se) {
		if (p1.se < p2.se)
			res = {p1.se, p1.se};
		else
			res = {p1.fi, p1.fi};
	}
	return res;
}

struct Segtree {	// range addition, range sum query
	int sz;
	vector<ii> lazy;	// store (a, b)
	Segtree(int N) {
		sz = 1;
		while (sz < N)
			sz *= 2;
		lazy = vector<ii>(2 * sz, {-1e9, 1e9});
	}
	void push(int id, int left, int right) {
		if (right - left == 1)
			return;
		lazy[2 * id + 1] = combine(lazy[id], lazy[2 * id + 1]);
		lazy[2 * id + 2] = combine(lazy[id], lazy[2 * id + 2]);
		lazy[id] = {-1e9, 1e9};
	}
	void range_upd(int qleft, int qright, ii val, int id, int left, int right) {
		if (qleft <= left && right <= qright) {
			lazy[id] = combine(val, lazy[id]);
			return;
		}
		if (qright <= left || right <= qleft)
			return;
		push(id, left, right);
		int mid = (left + right) / 2;
		range_upd(qleft, qright, val, 2 * id + 1, left, mid);
		range_upd(qleft, qright, val, 2 * id + 2, mid, right);
	}
	void range_upd(int qleft, int qright, ii val) {
		range_upd(qleft, qright, val, 0, 0, sz);
	}
	ii query(int pos, int id, int left, int right) {
		if (right - left == 1) {
			return lazy[id];
		}
		push(id, left, right);
		int mid = (left + right) / 2;
		if (pos < mid)
			return query(pos, 2 * id + 1, left, mid);
		else
			return query(pos, 2 * id + 2, mid, right);
	}
	ii query(int pos) {
		return query(pos, 0, 0, sz);
	}
};

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
	Segtree st(N);
	for (int i = 0; i < K; i++) {
		if (op[i] == 1)
			st.range_upd(left[i], right[i] + 1, {height[i], 1e9});
		else
			st.range_upd(left[i], right[i] + 1, {-1e9, height[i]});
	}
/*	for (int i = 0; i < N; i++) {
		ii res = st.query(i);
		cout<<i<<": "<<res.fi<<" "<<res.se<<endl;
	}*/
	for (int i = 0; i < N; i++) {
		finalHeight[i] = max(st.query(i).fi, 0);
	}
	return;
}

// f(x) = a, x, or b (piecewise)
// represent function
// store as (a, b), where a can be -inf and b can be +inf

// query: returns (a, b)


// (a, b) [later] done on (c, d)
// becomes (max(a, c), min(b, d))
// if min(b, d) > max(a, c), know that [a, b] and [c, d] are disjoint
// if b < d, then becomes (b, b); otherwise becomes (c, c)

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