Submission #520078

#	Time	Username	Problem	Language	Result	Execution time	Memory
520078		akhan42	Wall (IOI14_wall)	C++17	100 / 100	1227 ms	89096 KiB

wall

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


struct Seg {
	int n;
	vi mx, mn;
	const int INF = 1000 * 1000;

	Seg(int n): n(n) {
		mx.assign(4 * n, -INF);
		mn.assign(4 * n, INF);

		build();
	}

	void build(int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			mn[v] = mx[v] = 0;
			return;
		}
		int tm = (tl + tr) / 2;

		build(2 * v, tl, tm);
		build(2 * v + 1, tm + 1, tr);
	}

	void prop_ch(int v, int vc) {
		if(mn[vc] < mx[v])
			mn[vc] = mx[vc] = mx[v];
		else if(mx[vc] > mn[v])
			mn[vc] = mx[vc] = mn[v];
		else {
			maxeq(mx[vc], mx[v]);
			mineq(mn[vc], mn[v]);
		}
	}

	void propagate(int v, int tl, int tr) {
		if(tl == tr)
			return;

		prop_ch(v, 2 * v);
		prop_ch(v, 2 * v + 1);
		mn[v] = INF;
		mx[v] = -INF;
	}

	void update(int l, int r, int ph, int h, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r)
			return;

		if(tl == l && r == tr) {
//			cout << l << ' ' << r << '\n';
			if(tl == tr) {
				if((ph == 1 && mn[v] < h) || (ph == 2 && mx[v] > h))
					mn[v] = mx[v] = h;
			} else {
				if(ph == 1)
					mx[v] = h;
				else
					mn[v] = h;
			}
			return;
		}
		int tm = (tl + tr) / 2;

		update(l, min(r, tm), ph, h, 2 * v, tl, tm);
		update(max(l, tm + 1), r, ph, h, 2 * v + 1, tm + 1, tr);
	}

	int at(int p, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);

		if(tl == tr) {
			return mn[v];
		}
		int tm = (tl + tr) / 2;

		if(p <= tm)
			return at(p, 2 * v, tl, tm);
		else
			return at(p, 2 * v + 1, tm + 1, tr);
	}
};


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

	forn(i, k) {
		seg.update(left[i], right[i], op[i], height[i]);
	}

	forn(i, n)
		finalHeight[i] = seg.at(i);
}


void solve() {
	int n, k;
	cin >> n >> k;

	int op[k], left[k], right[k], height[k], finalHeight[k];
	forn(i, k)
		cin >> op[i] >> left[i] >> right[i] >> height[i];

	buildWall(n, k, op, left, right, height, finalHeight);
	forn(i, n)
		cout << finalHeight[i] << ' ';
	cout << endl;
}

//
//int main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(nullptr);
////	cout.tie(nullptr);
//
////	freopen("optmilk.in", "r", stdin);
////	freopen("optmilk.out", "w", stdout);
//
//	int t = 1;
////	cin >> t;
//	while(t--) {
//		solve();
//	}
//}

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