Submission #1000600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000600		biximo	Building 4 (JOI20_building4)	C++17	0 / 100	1 ms	6492 KiB

building4

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int A[N], B[N], LIS[N], n, minv[N], maxv[N], bt[N];
string ans;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    n <<= 1;
    priority_queue<array<int,2>> miv, mav;
    for(int i = 1; i <= n; i ++) {
    	cin >> A[i];
    }
    for(int i = 1; i <= n; i ++) {
    	cin >> B[i];
    }
    for(int i = 1; i <= n;) {
    	int j = i+1;
    	while(j <= n && B[j] >= B[j-1]) j ++;
    	for(int k = i; k < j; k ++) {
    		LIS[k] = j-1;
    	}
    	i = j;
    }
    for(int i = 1; i <= n; i ++) {
    	while(miv.size() && LIS[miv.top()[1]+1] != LIS[i-1]) miv.pop();
    	while(mav.size() && LIS[mav.top()[1]+1] != LIS[i-1]) mav.pop();
    	if(A[i-1] <= A[i]) {
    		minv[i] = minv[i-1]+1;
    		maxv[i] = maxv[i-1]+1;
    		bt[i] = i-1;
    	} else {
    		minv[i] = N;
    		maxv[i] = -N;
    	}
    	if(miv.size() && B[i-1] <= A[i]) minv[i] = min(minv[i], 1-miv.top()[0]);
    	if(mav.size() && B[i-1] <= A[i]) {
    		maxv[i] = max(maxv[i], mav.top()[0]+1);
    		if(maxv[i] == mav.top()[0]+1) {
    			bt[i] = mav.top()[1];
    		}
    	}
    	if(B[i] >= A[i-1]) {
    		miv.push({-minv[i-1],i-1});
    		mav.push({maxv[i-1], i-1});
    	}
    }
    ans.resize(n);
    bool okb = 1;
    for(int i = n; i >= 1; i --) {
    	if(okb && maxv[i] == n/2 && (i == n || A[i] <= B[i+1])) {
    		int c = i;
    		while(c) {
    			ans[c-1] = 'A';
    			c = bt[c];
    		}
    		for(int j = 0; j < n; j ++) {
    			if(ans[j] == 'A') cout << 'A';
    			else cout << 'B';
    		}
    		return 0;
    	}
    	if(i != n && B[i] > B[i+1]) okb = 0;
    }
    cout << -1;
}

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