제출 #258747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258747		Saboon	건물 4 (JOI20_building4)	C++14	11 / 100	2081 ms	32816 KiB

building4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;
const int inf = 1e9 + 1;

int a[maxn], b[maxn];
pair<int,int> A[maxn], B[maxn];
int seg[4*maxn], lazy[4*maxn];

void shift(int);

pair<int,int> get(int id, int L, int R, int x){
	if (seg[id] > x)
		return {-1,-1};
	if (L+1 == R)
		return {L,R};
	shift(id);
	int mid = (L + R) >> 1;
	auto it1 = get(2*id+0, L, mid, x);
	auto it2 = get(2*id+1, mid, R, x);
	if (it1 == make_pair(-1,-1))
		return it2;
	if (it2 == make_pair(-1,-1))
		return it1;
	return {it1.first, it2.second};
}

void change(int id, int L, int R, int l, int r, int val){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		seg[id] = val;
		lazy[id] = val;
		return;
	}
	shift(id);
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, l, r, val);
	change(2*id+1, mid, R, l, r, val);
	seg[id] = min(seg[2*id+0], seg[2*id+1]);
}

void shift(int id){
	if (lazy[id] == 0)
		return;
	change(2*id+0, 0, 1, 0, 1, lazy[id]);
	change(2*id+1, 0, 1, 0, 1, lazy[id]);
	lazy[id] = 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < 2*n; i++)
		cin >> a[i];
	for (int i = 0; i < 2*n; i++)
		cin >> b[i];
	for (int i = 1; i < 2*n; i++)
		if (max(a[i],b[i]) < min(a[i-1],b[i-1]))
			return cout << -1 << endl, 0;
	change(1, 0, 2*n+1, 1, 2*n+1, inf);
	for (int i = 0; i < 2*n; i++){
		auto ita = get(1, 0, 2*n+1, a[i]);
		auto itb = get(1, 0, 2*n+1, b[i]);
		A[i] = ita, B[i] = itb;
		if (ita == make_pair(-1,-1) and itb == make_pair(-1,-1))
			return cout << -1 << endl, 0;
		if (a[i] < b[i]){
			if (ita == make_pair(-1,-1)){
				change(1, 0, 2*n+1, 0, 2*n+1, inf);
				change(1, 0, 2*n+1, itb.first+1, itb.second+1, b[i]);
				continue;
			}
			change(1, 0, 2*n+1, 0, 2*n+1, inf);
			change(1, 0, 2*n+1, itb.first+1, itb.second+1, b[i]);
			change(1, 0, 2*n+1, ita.first, ita.second, a[i]);
		}
		else{
			if (itb == make_pair(-1,-1)){
				change(1, 0, 2*n+1, 0, 2*n+1, inf);
				change(1, 0, 2*n+1, ita.first, ita.second, a[i]);
				continue;
			}
			change(1, 0, 2*n+1, 0, 2*n+1, inf);
			change(1, 0, 2*n+1, ita.first, ita.second, a[i]);
			change(1, 0, 2*n+1, itb.first+1, itb.second+1, b[i]);
		}
	}
	auto it = get(1, 0, 2*n+1, inf-1);
	if (it.first == -1 or it.first > n or it.second <= n)
		return cout << -1 << endl, 0;
	int now = n;
	string s;
	int last = inf;
	for (int i = 2*n-1; i >= 0; i--){
		if (b[i] <= last and (A[i].first == -1 or A[i].first > now or A[i].second <= now or a[i] > last)){
			s += 'B';
			now --;
			last = b[i];
			continue;
		}
		s += 'A';
		last = a[i];
	}
	reverse(s.begin(),s.end());
	cout << s << endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89