Submission #221536

#	Time	Username	Problem	Language	Result	Execution time	Memory
221536		staniewzki	Wall (IOI14_wall)	C++14	100 / 100	1410 ms	108668 KiB

wall

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;

#include "wall.h"

#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

struct Node {
	int low = 0, high = 1e5;
	int lazy_low = 0, lazy_high = 1e5;
	int sz = 1;
};

struct Tree {
	vector<Node> tree;
	int sz = 1;

	Tree(int n) {
		while(sz < n)
			sz *= 2;
		tree.resize(sz * 2);
		for(int i = sz - 1; i >= 1; i--)
			tree[i].sz = tree[i * 2].sz * 2;
	}

	void apply(int v, int low, int high) {
		auto adjust = [&](int &x) {
			if(x < low) x = low;
			if(high < x) x = high;
		};

		adjust(tree[v].low);
		adjust(tree[v].high);
		adjust(tree[v].lazy_low);
		adjust(tree[v].lazy_high);
	}

	void propagate(int v) {
		REP(i, 2) 
			apply(v * 2 + i, tree[v].lazy_low, tree[v].lazy_high);
		tree[v].lazy_low = 0, tree[v].lazy_high = 1e5;
	}

	void update(int l, int r, int val_l, int val_r, int v = 1) {
		if(l == 0 && r == tree[v].sz - 1) {
			apply(v, val_l, val_r);
			return;
		}

		propagate(v);

		int m = tree[v].sz / 2;
		if(r < m) update(l, r, val_l, val_r, v * 2);
		else if(m <= l) update(l - m, r - m, val_l, val_r, v * 2 + 1);
		else {
			update(l, m - 1, val_l, val_r, v * 2),
			update(0, r - m, val_l, val_r, v * 2 + 1);
		}
	}

	void prop_all(int v = 1) {
		if(tree[v].sz == 1) return;
		propagate(v);
		REP(i, 2) 
			prop_all(v * 2 + i);
	}

	int get(int v) {
		return tree[v + sz].low;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	Tree tree(n);

	REP(i, k) {
		int val_l = (op[i] == 1 ? height[i] : 0);
		int val_r = (op[i] == 2 ? height[i] : 1e5);
		tree.update(left[i], right[i], val_l, val_r);
	}

	tree.prop_all();
	REP(i, n) finalHeight[i] = tree.get(i);
}

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