Submission #1062837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062837		MrNanama	Wall (IOI14_wall)	C++17	100 / 100	1728 ms	224648 KiB

wall

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;

template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}

vector<ll> arr;
vector<ll> seg;
vector<ll> lazy_set;
vector<ll> lazy_add;
vector<ll> lazy_rmv;

void pushdown(ll ind, ll l, ll r){
	if(l == r){return;}

	if(lazy_set[ind] != -1){
		lazy_set[2*ind] = lazy_set[ind];
		lazy_add[2*ind] = 0;
		lazy_rmv[2*ind] = LLONG_MAX;
	}else{
		if(lazy_set[2*ind] != -1){
			lazy_set[2*ind] = max<ll>(lazy_set[2*ind], lazy_add[ind]);
			lazy_set[2*ind] = min<ll>(lazy_set[2*ind], lazy_rmv[ind]);
		}else{
			if(lazy_add[ind] >= lazy_rmv[2*ind]){
				lazy_set[2*ind] = lazy_add[ind];
				lazy_add[2*ind] = 0;
				lazy_rmv[2*ind] = LLONG_MAX;
			}else if(lazy_rmv[ind] <= lazy_add[2*ind]){
				lazy_set[2*ind] = lazy_rmv[ind];
				lazy_add[2*ind] = 0;
				lazy_rmv[2*ind] = LLONG_MAX;
			}else{
				lazy_add[2*ind] = max<ll>(lazy_add[ind], lazy_add[2*ind]);
				lazy_rmv[2*ind] = min<ll>(lazy_rmv[ind], lazy_rmv[2*ind]);
			}
		}
	}

	if(lazy_set[ind] != -1){
		lazy_set[2*ind+1] = lazy_set[ind];
		lazy_add[2*ind+1] = 0;
		lazy_rmv[2*ind+1] = LLONG_MAX;
	}else{
		if(lazy_set[2*ind+1] != -1){
			lazy_set[2*ind+1] = max<ll>(lazy_set[2*ind+1], lazy_add[ind]);
			lazy_set[2*ind+1] = min<ll>(lazy_set[2*ind+1], lazy_rmv[ind]);
		}else{
			if(lazy_add[ind] >= lazy_rmv[2*ind+1]){
				lazy_set[2*ind+1] = lazy_add[ind];
				lazy_add[2*ind+1] = 0;
				lazy_rmv[2*ind+1] = LLONG_MAX;
			}else if(lazy_rmv[ind] <= lazy_add[2*ind+1]){
				lazy_set[2*ind+1] = lazy_rmv[ind];
				lazy_add[2*ind+1] = 0;
				lazy_rmv[2*ind+1] = LLONG_MAX;
			}else{
				lazy_add[2*ind+1] = max<ll>(lazy_add[ind], lazy_add[2*ind+1]);
				lazy_rmv[2*ind+1] = min<ll>(lazy_rmv[ind], lazy_rmv[2*ind+1]);
			}
		}
	}

	//clear all lazys
	lazy_set[ind] = -1;
	lazy_add[ind] = 0;
	lazy_rmv[ind] = LLONG_MAX;
}

void upd_add(ll ind, ll val, ll tl, ll tr, ll l, ll r){
	pushdown(ind, l, r);
	if(max<ll>(l,tl) > min<ll>(r,tr)){return;}

	if(tl <= l && r <= tr){
		if(lazy_set[ind] != -1){
			lazy_set[ind] = max<ll>(lazy_set[ind], val);
		}else if(lazy_rmv[ind] <= val){
			lazy_set[ind] = val;
			lazy_add[ind] = 0;
			lazy_rmv[ind] = LLONG_MAX;
		}else{
			lazy_add[ind] = max<ll>(lazy_add[ind], val);
		}
	}else{
		ll m = (r-l)/2+l;
		upd_add(2*ind, val, tl, tr, l, m);
		upd_add(2*ind+1, val, tl, tr, m+1, r);
	}

	pushdown(ind,l,r);
}

void upd_rmv(ll ind, ll val, ll tl, ll tr, ll l, ll r){
	pushdown(ind, l, r);
	if(max<ll>(l,tl) > min<ll>(r,tr)){return;}

	if(tl <= l && r <= tr){
		if(lazy_set[ind] != -1){
			lazy_set[ind] = min<ll>(lazy_set[ind], val);
		}else if(lazy_add[ind] >= val){
			lazy_set[ind] = val;
			lazy_add[ind] = 0;
			lazy_rmv[ind] = LLONG_MAX;
		}else{
			lazy_rmv[ind] = min<ll>(lazy_rmv[ind], val);
		}
	}else{
		ll m = (r-l)/2+l;
		upd_rmv(2*ind, val, tl, tr, l, m);
		upd_rmv(2*ind+1, val, tl, tr, m+1, r);
	}

	pushdown(ind,l,r);
}


void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
		
	lazy_set.assign(4*n, -1);
	lazy_add.assign(4*n, 0);
	lazy_rmv.assign(4*n, LLONG_MAX);


	for(ll i=0; i<k; i++){

		if(op[i] == 1){
			//adding
			upd_add(1,height[i],left[i],right[i],0,n-1);

		}else{
			//removing
			upd_rmv(1,height[i],left[i],right[i],0,n-1);
		}

		/*
		cout << i << endl;
		cout << lazy_set << endl;
		cout << lazy_add << endl;
		cout << lazy_rmv << endl;
		*/
	}


	function<ll(ll,ll,ll)> dfs;

	dfs = [&](ll ind, ll l, ll r){
		pushdown(ind, l, r);
		if(l != r){
			ll m = (r-l)/2+l;
			dfs(2*ind, l, m);
			dfs(2*ind+1, m+1, r);
		}else{
			if(lazy_set[ind] != -1){
				finalHeight[l] = lazy_set[ind];
			}else{
				finalHeight[l] = lazy_add[ind];
			}
		}

		return 0;
	};
	dfs(1, 0, n-1);

}

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