Submission #630255

#	Time	Username	Problem	Language	Result	Execution time	Memory
630255		Arnch	Building 4 (JOI20_building4)	C++17	100 / 100	592 ms	87968 KiB

building4

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7;

int n;
int a[N], b[N];
int dp[N], ri[N];
bool mark[N], vis[N];
vector<int> vc;


struct node {
	int lz, cnt;
	node() {
		cnt = lz = 0;
	}
} x[N << 2];

void build(int l = 0, int r = 2 * n, int v = 1) {
	if(r - l < 2) {
		if(!mark[l]) {
			if(vc[l] == a[l]) x[v].cnt = -2;
			else x[v].cnt = 2;
		}	
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2 * v), build(mid, r, 2 * v + 1);
	x[v].cnt = x[2 * v].cnt + x[2 * v + 1].cnt;
}
void put(int l, int r, int v) {
	if(x[v].lz == 0) return;
	x[2 * v].cnt = 0, x[2 * v].lz = 1;
	x[2 * v + 1].cnt = 0, x[2 * v + 1].lz = 1;
	x[v].lz = 0;
}
void change(int s, int e, int l = 0, int r = 2 * n, int v = 1) {
	if(r <= s || l >= e) return;
	if(l >= s && r <= e) {
		x[v].cnt = 0, x[v].lz = 1;
		return;
	}
	put(l, r, v);
	int mid = (l + r) >> 1;
	change(s, e, l, mid, 2 * v), change(s, e, mid, r, 2 * v + 1);
	x[v].cnt = x[2 * v].cnt + x[2 * v + 1].cnt;
}
int get(int s, int e, int l = 0, int r = 2 * n, int v = 1) {
	if(r <= s || l >= e) return 0;
	if(l >= s && r <= e) return x[v].cnt;
	put(l, r, v);
	int mid = (l + r) >> 1;
	return get(s, e, l, mid, 2 * v) + get(s, e, mid, r, 2 * v + 1);
}

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
	
	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 = 0; i < 2 * n; i++) {
		if(!vc.empty() && max(a[i], b[i]) < vc.back()) return cout<<-1, 0;

		int val = min(a[i], b[i]);
		if(vc.empty() || vc.back() <= val) vc.push_back(val);
		else vc.push_back(max(a[i], b[i]));
	}

	string s = "";
	for(int j = 0; j < Sz(vc); j++) {
		if(vc[j] == a[j]) s.push_back('A');
		else s.push_back('B');
	}

	int cnt = 0;
	for(int j = 0; j < Sz(vc); j++) {
		if(vc[j] == a[j]) cnt++;
		else cnt--;
	}
	if(cnt == 0) {
		return cout<<s, 0;
	}

	vector<pair<int, pair<int, int> > > nap;
	for(int i = 2 * n - 1; i >= 0; i--) {
		if(vc[i] != min(a[i], b[i])) continue;

		if(i == 2 * n - 1) {
			if(vc[i] == a[i]) dp[i] = -2;
			else dp[i] = 2;
			ri[i] = i;
			
			nap.push_back({dp[i], {i, i}});
			continue;
		}
		if(max(a[i], b[i]) > max(a[i + 1], b[i + 1])) {
			mark[i] = 1;
			continue;
		}
		if(max(a[i], b[i]) <= vc[i + 1]) {
			if(vc[i] == a[i]) dp[i] = -2;
			else dp[i] = 2;
			ri[i] = i;

			nap.push_back({dp[i], {i, i}});
			continue;
		}
		if(mark[i + 1]) {
			mark[i] = 1;
			continue;
		}
		dp[i] = dp[i + 1];
		if(vc[i] == a[i]) dp[i] -= 2;
		else dp[i] += 2;
		ri[i] = ri[i + 1];

		nap.push_back({dp[i], {i, ri[i]}});
	}

	build();
	
	sort(All(nap));
	if(cnt < 0) {
		while(!nap.empty() && cnt < 0) {
			int val = nap.back().first, l = nap.back().second.first, r = nap.back().second.second;
			nap.pop_back();

			val = get(l, r + 1);

			if(val < 0) {
				//return cout<<-1, 0;
				continue;
			}
			if(val + cnt > 0) continue;
			cnt += val;
			change(l, r + 1);
		}
		for(int i = 0; i < 2 * n; i++) {
			if(mark[i]) continue;
			if(get(i, i + 1) == 0) {
				if(s[i] == 'A') s[i] = 'B';
				else s[i] = 'A';
			}
		}
		if(cnt < 0) return cout<<-1, 0;
		return cout<<s, 0;
	}
	reverse(All(nap));
	while(!nap.empty() && cnt > 0) {
		int val = nap.back().first, l = nap.back().second.first, r = nap.back().second.second;
		nap.pop_back();

		val = get(l, r + 1);

		if(val > 0) {
			//return cout<<-1, 0;
			continue;
		}
		if(val + cnt < 0) continue;
		cnt += val;
		change(l, r + 1);
	}
	for(int i = 0; i < 2 * n; i++) {
		if(mark[i]) continue;
		if(get(i, i + 1) == 0) {
			if(s[i] == 'A') s[i] = 'B';
			else s[i] = 'A';
		}
	}
	if(cnt > 0) return cout<<-1, 0;
	return cout<<s, 0;

}

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