Submission #835541

#	Time	Username	Problem	Language	Result	Execution time	Memory
835541		mat_jur	Wall (IOI14_wall)	C++17	0 / 100	233 ms	9240 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	int base = 1;
	while (base < n) base *= 2;
	struct Node {
		int mn, mx;
		int lzmn, lzmx;
		Node() {lzmn = -1; lzmx = -1; mn = mx = 0;}
	};
	vector<Node> tree(2*base);
	auto minn = [&](int a, int b) {
		if (a == -1) return b;
		return min(a, b);
	};
	auto push_to_sons = [&](int v) {
		int l = tree[v].lzmn, r = tree[v].lzmx;
		if (r == -1) return;
		tree[2*v].mn = min(max(tree[2*v].mn, l), r);
		tree[2*v+1].mn = min(max(tree[2*v+1].mn, l), r);
		tree[2*v].mx = max(min(tree[2*v].mx, r), l);
		tree[2*v+1].mx = max(min(tree[2*v+1].mx, r), l);
		tree[2*v].lzmn = max(tree[2*v].lzmn, l);
		tree[2*v+1].lzmn = max(tree[2*v+1].lzmn, l);
		tree[2*v].lzmx = minn(tree[2*v].lzmx, r);
		tree[2*v+1].lzmx = minn(tree[2*v+1].lzmx, r);
		tree[v].lzmn = -1; tree[v].lzmx = -1;
	};
	function<void(int, int, int, int, int, int)> updatemn = [&](int l, int r, int x, int v, int a, int b) {
		if (r < a || b < l) return;
		if (l <= a && b <= r) {
			tree[v].mn = max(tree[v].mn, x);	
			tree[v].mx = max(tree[v].mx, x);	
			tree[v].lzmn = max(tree[v].lzmn, x);	
			tree[v].lzmx = max(tree[v].lzmx, x);	
			return;
		}
		push_to_sons(v);
		int mid = (a+b)/2;
		updatemn(l, r, x, 2*v, a, mid); updatemn(l, r, x, 2*v+1, mid+1, b);
		tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
		tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
	};
	function<void(int, int, int, int, int, int)> updatemx = [&](int l, int r, int x, int v, int a, int b) {
		if (r < a || b < l) return;
		if (l <= a && b <= r) {
			tree[v].mn = min(tree[v].mn, x);	
			tree[v].mx = min(tree[v].mx, x);	
			tree[v].lzmn = minn(tree[v].lzmn, x);	
			tree[v].lzmx = minn(tree[v].lzmx, x);	
			return;
		}
		push_to_sons(v);
		int mid = (a+b)/2;
		updatemx(l, r, x, 2*v, a, mid); updatemx(l, r, x, 2*v+1, mid+1, b);
		tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
		tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
	};
	REP(i, k) {
		if (op[i] == 1) {
			updatemn(left[i], right[i], height[i], 1, 0, base-1);
		}
		else {
			updatemx(left[i], right[i], height[i], 1, 0, base-1);
		}
	}
	FOR(i, 1, base-1) {
		push_to_sons(i);
	}
	FOR(i, base, base+n-1) {
		assert(tree[i].mn == tree[i].mx);
//		cerr << tree[i].mn << ' ' << tree[i].mx << '\n';
		finalHeight[i-base] = tree[i].mn;
	}
}
/*
#ifdef LOCAL
int main () {
	int n, k;
	cin >> n >> k;
	REP(i, k) {
		int 
	}
}
#endif
*/

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