제출 #488648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488648		grt	벽 (IOI14_wall)	C++17	24 / 100	395 ms	14528 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int INF = 1e9;
int n, k;

struct Node {
	int h, H;
	bool which;
};

Node T[(1 << 21)];

void prop(int x) {
	if(T[x].h != 0 || T[x].H != INF) {
		T[2*x].which = T[x].which;
		T[2*x+1].which = T[x].which;
	}
	T[2*x].h = max(T[2*x].h, T[x].h);
	T[2*x].H = min(T[2*x].H, T[x].H);
	T[2*x+1].h = max(T[2*x+1].h, T[x].h);
	T[2*x+1].H = min(T[2*x+1].H, T[x].H);
	T[x].h = 0; T[x].H = INF;
}

void init(int l, int r, int v) {
	T[v].h = 0; T[v].H = INF;
	if(l == r) return;
	int mid = (l + r)/2;
	init(l,mid,v*2);
	init(mid+1,r,v*2+1);
}

void upd(int a, int b, int l, int r, int v, int x, bool t) {
	if(a <= l && r <= b) {
		if(!t) {
			T[v].h = max(T[v].h, x);
			
		} else {
			T[v].H = min(T[v].H, x);
		}
		T[v].which = t;
		return;
	}
	prop(v);
	int mid = (l + r) / 2;
	if(a <= mid) upd(a,b,l,mid,v*2,x,t);
	if(mid < b) upd(a,b,mid+1,r,v*2+1,x,t);
}

int res[2'000'000 + 10];

void rec(int l, int r, int v) {
	if(l == r) {
		if(T[v].h < T[v].H) res[l] = T[v].h;
		else if(!T[v].which) res[l] = T[v].h;
		else res[l] = T[v].H;
		return;
	}
	prop(v);
	int mid = (l+r)/2;
	rec(l,mid,v*2);
	rec(mid+1,r,v*2+1);
}


void buildWall(int _n, int _k, int op[], int l[], int r[], int hei[], int ans[]) {
	n = _n; k = _k;
	init(0, n-1, 1);
	for(int i = 0; i < k; ++i) {
		upd(l[i], r[i], 0, n-1, 1, hei[i], op[i] - 1);
	}
	rec(0,n-1,1);
	for(int i = 0; i < n; ++i) {
		ans[i] = res[i];
	}
}


//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int _n, _k;
	//cin >> _n >> _k;
	//vi op(_k), 
	//for(int 
//}

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