제출 #1014175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014175		AmirAli_H1	벽 (IOI14_wall)	C++17	100 / 100	726 ms	102416 KiB

wall

// In the name of Allah

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo = 1e18 + 4;
const int maxn = (1 << 21) + 4;

int n, q;
pll t[2 * maxn];

void upd_lazy(int v, pll x) {
	if (max(t[v].F, x.F) <= min(t[v].S, x.S)) {
		t[v].F = max(t[v].F, x.F); t[v].S = min(t[v].S, x.S);
	}
	else {
		if (t[v].S < x.F) t[v] = Mp(x.F, x.F);
		else t[v] = Mp(x.S, x.S);
	}
}

void shift(int v) {
	pll x = t[v]; t[v] = Mp(-oo, oo);
	if (x == Mp(-oo, oo)) return ;
	for (int u : {2 * v + 1, 2 * v + 2}) {
		upd_lazy(u, x);
	}
}

void build(int v, int tl, int tr) {
	t[v] = Mp(-oo, oo);
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

void upd_val(int v, int tl, int tr, int l, int r, pll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		upd_lazy(v, x);
		return ;
	}
	shift(v);
	int mid = (tl + tr) / 2;
	upd_val(2 * v + 1, tl, mid, l, r, x); upd_val(2 * v + 2, mid, tr, l, r, x);
}

ll get_val(int v, int tl, int tr, int i) {
	if (tr - tl == 1) {
		ll x = 0;
		x = max(x, t[v].F); x = min(x, t[v].S);
		return x;
	}
	shift(v);
	int mid = (tl + tr) / 2;
	if (i < mid) return get_val(2 * v + 1, tl, mid, i);
	else return get_val(2 * v + 2, mid, tr, i);
}

void buildWall(int Nx, int Qx, int op[], int lq[], int rq[], int hq[], int ans[]) {
	n = Nx; q = Qx;
	build(0, 0, n);
	for (int i = 0; i < q; i++) {
		rq[i]++;
		if (op[i] == 1) {
			upd_val(0, 0, n, lq[i], rq[i], Mp(hq[i], oo));
		}
		else {
			upd_val(0, 0, n, lq[i], rq[i], Mp(-oo, hq[i]));
		}
	}
	for (int i = 0; i < n; i++) ans[i] = get_val(0, 0, n, i);
}

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