Submission #258749

#	Time	Username	Problem	Language	Result	Execution time	Memory
258749		Saboon	건물 4 (JOI20_building4)	C++14	100 / 100	365 ms	28656 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];

vector<pair<int,pair<int,int>>> vec;

pair<int,int> get(int id, int L, int R, int x){
	pair<int,int> ret = {-1,-1};
	for (auto it : vec){
		if (it.first > x)
			continue;
		if (ret == make_pair(-1,-1))
			ret = it.second;
		else{
			ret.first = min(ret.first, it.second.first);
			ret.second = max(ret.second, it.second.second);
		}
	}
	return ret;
}

void change(int id, int L, int R, int l, int r, int val){
	if (val == inf){
		vec.clear();
		return;
	}
	vec.push_back({val,{l,r}});
}

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, 0, 1, 0);
	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: 89 / 89