oj.uz

Submission #1062773

# Submission time Handle Problem Language Result Execution time Memory
1062773 2024-08-17T10:38:18 Z MrNanama Wall (IOI14_wall) C++17
0 / 100
 82 ms 8048 KB 
#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{
			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{
			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);
		}
	}


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

	dfs = [&](ll ind, ll l, ll 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 82 ms 8048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -