Submission #1000602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000602		biximo	Building 4 (JOI20_building4)	C++17	0 / 100	2032 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;
void reconstruct(int st) {
	priority_queue<array<int,3>> pq;
	for(auto&i: ans) i = 'B';
	int c = st, cv = n/2, prev;
	while(c) {
		ans[c-1] = 'A';
		if(minv[c-1] <= cv - 1 && cv - 1 <= maxv[c-1]) {
			prev = c;
			c --;
			cv --;
			continue;
		}
		// cout << c << " " << cv << "\n";
		if(c == st || LIS[prev-1] != LIS[c-1]) {
			for(int i = c-2; i >= 0 && LIS[i+1] == LIS[c-1]; i --) {
				if(A[i] <= B[i+1]) pq.push({maxv[i],minv[i],i});
			}
			// cout << "Woah.?\n";
		}
		assert(pq.size());
		while(pq.top()[2] >= c) pq.pop();
		while(pq.top()[1] > cv-1) pq.pop();
		cv --;
		prev = c;
		c = pq.top()[2];
	}
	cout << 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;
    	} 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(B[i] >= A[i-1]) {
    		miv.push({-minv[i-1],i-1});
    		mav.push({maxv[i-1], i-1});
    	}
    }
    ans.resize(n);
    for(int i = n; i >= 1; i --) {
    	// cout << minv[i] << " " << maxv[i] << "\n";
    	if(minv[i] <= n/2 && n/2 <= maxv[i]&& (i == n || A[i] <= B[i+1])) {
    		reconstruct(i);
    		return 0;
    	}
    	if(i != n && B[i] > B[i+1]) break;
    }
    cout << -1;
}

Compilation message (stderr)

building4.cpp: In function 'void reconstruct(int)':
building4.cpp:19:25: warning: 'prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
   19 |   if(c == st || LIS[prev-1] != LIS[c-1]) {
      |                     ~~~~^~

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