제출 #351239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351239		NachoLibre	벽 (IOI14_wall)	C++14	0 / 100	1479 ms	70052 KiB

wall

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

const int R = 100000;

struct vyv {
	vyv *l, *r;
	int xl, xr;
	vyv() {
		l = r = NULL;
		xl = 0;
		xr = R;
	}

	void P() {
		if(l == NULL) l = new vyv();
		if(r == NULL) r = new vyv();
		xl = max(l->xl, r->xl);
		xr = min(l->xr, r->xr);
		if(xl > xr) {
			if(l->xl > r->xr) {
				xl = xr = r->xr;
			} else if(l->xr < r->xl) {
				xl = xr = r->xl;
			} else {
				abort();
			}
		}
	}
} *rt;

int globk;
void gnk(int si, int vl, int vr, int l = 0, int r = globk - 1, vyv *&t = rt) {
	if(t == NULL) t = new vyv();
	if(l == r) {
		t->xl = vl;
		t->xr = vr;
		return;
	}
	int m = (l + r) / 2;
	if(m >= si) gnk(si, vl, vr, l, m, t->l);
	else gnk(si, vl, vr, m + 1, r, t->r);
	t->P();
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int dr[]) {
	globk = k;
	vector<pair<int, pair<int, int>>> v[n + 1];
	for(int i = 0; i < k; ++i) {
		int xl = 0, xr = R;
		if(op[i] == 1) {
			xl = h[i];
		} else {
			xr = h[i];
		}
		v[l[i]].push_back({i, {xl, xr}});
		v[r[i] + 1].push_back({i, {0, R}});
	}
	for(int i = 0; i < n; ++i) {
		for(auto p : v[i]) {
			gnk(p.first, p.second.first, p.second.second);
		}
		dr[i] = rt->xl;
	}
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

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