Submission #876283

#	Time	Username	Problem	Language	Result	Execution time	Memory
876283		Gray	Wall (IOI14_wall)	C++17	0 / 100	3028 ms	13932 KiB

wall

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

#include <bits/stdc++.h>
#define ll long long
#define ln "\n"
#define ff first
#define ss second
#define ld long double
using namespace std;

struct SegTree{
	struct node{
		int val;
		pair<int, int> mn;
		pair<int, int> mx;
		pair<int, pair<int, int>> upd;
	};
	vector<node> t;
	ll sz, rsz;
	SegTree(ll N){
		sz=1;
		rsz=N;
		while (sz<=N) sz*=2;
		sz*=2;
		t.resize(sz+1, {0, {-1, -1}, {-1, -1}, {0, {-1, -1}}});
	}
	void assign(ll v, ll typ, ll by, ll time){
		
		if (typ==-1){
			// cout << t[v].mn.ff << " " << t[v].mn.ss << " -> ";
			if (t[v].mn.ff==-1){
				t[v].mn = {by, time};
			}else if (t[v].mx.ff==-1){
				if (t[v].mn.ff>=by){
					t[v].mn = {by, time};
				}
			}else{
				if (t[v].mn.ss<t[v].mx.ss and t[v].mx.ff>t[v].mn.ff){
					t[v].mn = {by, time};
				}else{
					if (t[v].mn.ff>=by){
						t[v].mn = {by, time};
					}
				}
			}
			// cout << t[v].mn.ff << " " << t[v].mn.ss;
		}else{
			if (t[v].mx.ff==-1){
				t[v].mx = {by, time};
			}else if (t[v].mn.ff==-1){
				if (t[v].mx.ff<=by){
					t[v].mx = {by, time};
				}
			}else{
				if (t[v].mx.ss<t[v].mn.ss and t[v].mn.ff<t[v].mx.ff){
					t[v].mx = {by, time};
				}else{
					if (t[v].mx.ff<=by){
						t[v].mx = {by, time};
					}
				}
			}
		}	
	}
	void preprocess(ll tl, ll tr, ll v){
		// cout << "P" << endl;
		if (t[v].upd.ff!=0){
			// cout << "Upd: " << v << ln;
			// cout << tl << "-" << tr << " -> ";
			assign(v, t[v].upd.ff, t[v].upd.ss.ff, t[v].upd.ss.ss);
			// cout << ln;
			if (tl!=tr){
				ll tm = (tl+tr)/2;
				preprocess(tl, tm, v*2);
				preprocess(tm+1, tr, v*2+1);
				t[v*2].upd = t[v*2+1].upd = t[v].upd;
			}
			t[v].upd = {0, {-1, -1}};
		}
	}
	void update(ll tl, ll tr, ll v, ll l, ll r, ll typ, ll by, ll time){
		// cout << "U" << endl;
		preprocess(tl, tr, v);
		if (tl==l and tr==r){
			// cout << tl << "-" << tr << " -> ";
			assign(v, typ, by, time);
			// cout << ln;
			if (tl!=tr){
				ll tm = (tl+tr)/2;
				preprocess(tl, tm, v*2);
				preprocess(tm+1, tr, v*2+1);
				t[v*2].upd = {typ, {by, time}};
				t[v*2+1].upd = {typ, {by, time}};	
			}
			return;
		}
		if (l>r) return;
		ll tm = (tl+tr)/2;
		update(tl, tm, v*2, l, min(r, tm), typ, by, time);
		update(tm+1, tr, v*2+1, max(l, tm+1), r, typ, by, time);
	}
	void assemble(ll tl, ll tr, ll v, int ans[]){
		// cout << "AS " << tl << " " << tr << endl;
		preprocess(tl, tr, v);
		if (tl==tr){
			// cout << tl << ": " << t[v].mn.ff << " " << t[v].mn.ss << " | " << t[v].mx.ff << " " << t[v].mx.ss << ln;
			if (t[v].mn.ff!=-1 and t[v].mx.ff!=-1){
				if (t[v].mn.ss>t[v].mx.ss){
					t[v].val = t[v].mx.ff;
					t[v].val = min(t[v].mn.ff, t[v].val);
				}else{
					t[v].val = t[v].mn.ff;
					t[v].val = max(t[v].mx.ff, t[v].val);				
				}
			}else if (t[v].mx.ff!=-1){
				t[v].val = max(t[v].mx.ff, t[v].val);
			}else if (t[v].mn.ff!=-1){
				t[v].val = min(t[v].mn.ff, t[v].val);
			}
			
			ans[tl]=(t[v].val);
			return;
		}
		ll tm = (tl+tr)/2;
		assemble(tl, tm, v*2, ans);
		assemble(tm+1, tr, v*2+1, ans);
	}
	void update(ll l, ll r, ll typ, ll by, ll time){
		update(0, rsz-1, 1, l, r, typ, by, time);
	}
	void assemble(int ans[]){
		assemble(0, rsz-1, 1, ans);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree tr(n+1);
	for (ll i=0; i<k; i++){
		tr.update(left[i], right[i], (op[i]==2?-1:1), height[i], i);
	}
	tr.assemble(finalHeight);
}

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