제출 #1211024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211024		santi3223	Wall (IOI14_wall)	C++20	100 / 100	956 ms	97012 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define vl vector<ll>
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

vector<pll> t;
vl val;

void propagar(ll cur, ll l, ll r){
	if(l == r){
		val[l] = max(val[l], t[cur].fi);
		val[l] = min(val[l], t[cur].se);
		t[cur] = {0, 1e9};
		return;
	}
	ll i = 2*cur+1, j = 2*cur+2;
	t[i].fi = max(t[i].fi, t[cur].fi);
	t[i].se = max(t[i].fi, t[i].se);
	t[i].se = min(t[i].se, t[cur].se);
	t[i].fi = min(t[i].fi, t[i].se);
	t[j].fi = max(t[j].fi, t[cur].fi);
	t[j].se = max(t[j].se, t[j].fi);
	t[j].se = min(t[j].se, t[cur].se);
	t[j].fi = min(t[j].fi, t[j].se);
	t[cur] = {0, 1e9};
}

void update(ll i, ll tl, ll tr, ll l, ll r, ll v, ll tt){
	propagar(i, tl, tr);
	if(tr < l || r < tl){
		return;
	}
	if(l <= tl && tr <= r){
		if(tt == 1){
			t[i].fi = v;
		}
		else{
			t[i].se = v;
		}
		return;
	}
	ll mid = (tl+tr)/2;
	update(2*i+1, tl, mid, l, r, v, tt);
	update(2*i+2, mid+1, tr, l, r, v, tt);
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	t = vector<pll>(4*n, {0, 1e9});
	val = vl(n, 0);
	ff(i, 0, k){
		update(0, 0, n-1, left[i], right[i], height[i], op[i]);
	}
	ff(i, 0, n){
		update(0, 0, n-1, i, i, 0, 1);
	}
	ff(i, 0, n){
		finalHeight[i] = val[i];
		//cout << finalHeight[i];
	}
}

/*
int main(){
	ll n, k;
	cin >> n >> k;
	ll a[n], b[n], c[n], d[n];
	ff(i, 0, k){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	ll x[n];
	buildWall(n, k, a, b, c, d, x);
}

*/

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