Submission #878853

#	Time	Username	Problem	Language	Result	Execution time	Memory
878853		Gray	Wall (IOI14_wall)	C++17	100 / 100	533 ms	92448 KiB

wall

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include <cassert>
#define ll long long
#define ln "\n"
#define ff first
#define ss second
#define ld long double
const ll INF = 2e18;
const ll MOD = 1e9+7;
using namespace std;

struct SegTree{
	struct node{
		ll mn, mx;
	};
	node def = {INF, 0};
	vector<node> t;
	ll sz, rsz;
	SegTree(ll N){
		sz=1; while (sz<N) sz*=2;
		sz*=2; rsz=N;
		t.resize(sz, def);
	}
	
	void preprocess(ll v, ll chv1, ll chv2){
		if (t[v].mn != def.mn or t[v].mx!=def.mx){
			assert(t[v].mn>=t[v].mx);
			if (t[chv1].mx<t[v].mx){
				t[chv1].mx = t[v].mx;
				t[chv1].mn = min(t[chv1].mn, t[v].mn);
				if (t[chv1].mx>t[chv1].mn) t[chv1].mn = t[chv1].mx;
			}else if (t[chv1].mn>t[v].mn){
				t[chv1].mn = t[v].mn;
				t[chv1].mx = max(t[chv1].mx, t[v].mx);
				if (t[chv1].mx>t[chv1].mn) t[chv1].mx = t[chv1].mn;
			}else{

			}

			if (t[chv2].mx<t[v].mx){
				t[chv2].mx = t[v].mx;
				t[chv2].mn = min(t[chv2].mn, t[v].mn);
				if (t[chv2].mx>t[chv2].mn) t[chv2].mn = t[chv2].mx;
			}else if (t[chv2].mn>t[v].mn){
				t[chv2].mn = t[v].mn;
				t[chv2].mx = max(t[chv2].mx, t[v].mx);
				if (t[chv2].mx>t[chv2].mn) t[chv2].mx = t[chv2].mn;
			}else{

			}
		}
		t[v] = def;
	}
	void update_range(ll tl, ll tr, ll v, ll l, ll r, pair<ll, ll> &act){
		// cout << tl << " " << tr << " : " << l << " " << r << endl;
		if (tl!=tr) preprocess(v, v*2, v*2+1);
		if (tl==l and tr==r){
			if (act.ff==1){
				t[v].mx = max(t[v].mx, act.ss);
				t[v].mn = max(t[v].mn, t[v].mx);
			}else{
				t[v].mn = min(t[v].mn, act.ss);
				t[v].mx = min(t[v].mn, t[v].mx);
			}
			return;
		}
		if (l>r) return;
		ll tm = (tl+tr)/2;
		update_range(tl, tm, v*2, l, min(r, tm), act);
		update_range(tm+1, tr, v*2+1, max(l, tm+1), r, act);
	}
	void assemble(ll tl, ll tr, ll v, int ans[]){
		if (tl==tr){
			ans[tl] = (int)t[v].mx;
			return;
		}
		preprocess(v, v*2, v*2+1);
		ll tm = (tl+tr)/2;
		assemble(tl, tm, v*2, ans);
		assemble(tm+1, tr, v*2+1, ans);
	}
	void assemble(int ans[]){
		assemble(0, rsz-1, 1, ans);
	}
	void update(ll l, ll r, pair<ll, ll> act){
		update_range(0, rsz-1, 1, l, r, act);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree tr(n);
	for (ll i=0; i<k; i++){
		// cout << op[i] << endl;
		tr.update(left[i], right[i], {op[i], height[i]});	
		// tr.assemble(finalHeight);
		// for (ll j=0; j<n; j++) cout << finalHeight[j] << ' ';
		// cout << ln;
	}
	tr.assemble(finalHeight);
}

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