제출 #1138585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138585		Ekber_Ekber	벽 (IOI14_wall)	C++17	0 / 100	152 ms	133360 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
using namespace std;

struct point{
	int ma, mi;
};

constexpr int MAX = 2e+6 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX);

vector <point> t(4 * MAX, {0, 0}), lazy(4 * MAX, {-1, INF});
vector <int> h;

void push(int v) {
	if (lazy[v].ma != -1) {
		if (t[v*2].mi < lazy[v].ma) {
			t[v*2].mi = lazy[v].ma;
			t[v*2].ma = max(t[v*2].ma, t[v*2].mi);
			lazy[v*2].ma = max(lazy[v*2].ma, lazy[v].ma);
		}
		if (t[v*2+1].mi < lazy[v].ma) {
			t[v*2+1].mi = lazy[v].ma;
			t[v*2+1].ma = max(t[v*2+1].ma, t[v*2+1].mi);
			lazy[v*2+1].ma = max(lazy[v*2+1].ma, lazy[v].ma);
		}
		lazy[v].ma = -1;
	}
	if (lazy[v].mi != INF) {
		if (t[v*2].ma > lazy[v].mi) {
			t[v*2].ma = lazy[v].mi;
			t[v*2].mi = min(t[v*2].mi, t[v*2].ma);
			lazy[v*2].mi = min(lazy[v*2].mi, lazy[v].mi);
		}
		if (t[v*2+1].ma > lazy[v].mi) {
			t[v*2+1].ma = lazy[v].mi;
			t[v*2+1].mi = min(t[v*2+1].mi, t[v*2+1].ma);
			lazy[v*2+1].mi = min(lazy[v*2+1].mi, lazy[v].mi);
		}
		lazy[v].mi = INF;
	}
}

void update1(int v, int tl, int tr, int l, int r, int x) {		// increase
	if (l > r) return;
	if (tl == l && tr == r) {
		if (t[v].mi < x) {
			lazy[v].ma = max(lazy[v].ma, x);
			t[v].mi = x;
			t[v].ma = max(t[v].ma, t[v].mi);
		}
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	update1(v*2, tl, tm, l, min(r, tm), x);
	update1(v*2+1, tm+1, tr, max(l, tm+1), r, x);
	t[v].ma = max(t[v*2].ma, t[v*2+1].ma);
	t[v].mi = min(t[v*2].mi, t[v*2+1].mi);
}

void update2(int v, int tl, int tr, int l, int r, int x) {		// decrease
	if (l > r) return;
	if (tl == l && tr == r) {
		if (t[v].ma > x) {
			lazy[v].mi = min(lazy[v].mi, x);
			t[v].ma = x;
			t[v].mi = max(t[v].ma, t[v].mi);
		}
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	update2(v*2, tl, tm, l, min(r, tm), x);
	update2(v*2+1, tm+1, tr, max(l, tm+1), r, x);
	t[v].ma = max(t[v*2].ma, t[v*2+1].ma);
	t[v].mi = min(t[v*2].mi, t[v*2+1].mi);
}

void build(int v, int tl, int tr) {
	if (tl == tr) {
		h.pb(t[v].ma);
		return;
	}
	int tm = (tl + tr) / 2;
	build(v*2, tl, tm);
	build(v*2+1, tm+1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int z=0; z < k; z++) {
		if (op[z] == 1) {
			update1(1, 0, n-1, left[z], right[z], height[z]);
		}
		else {
			update2(1, 0, n-1, left[z], right[z], height[z]);
		}
	}
	build(1, 0, n-1);
	for (int i=0; i < n; i++) {
		finalHeight[i] = h[i];
	}
	return;
}

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