Submission #601043

#	Time	Username	Problem	Language	Result	Execution time	Memory
601043		cadmiumsky	Building 4 (JOI20_building4)	C++14	100 / 100	876 ms	56180 KiB

building4

#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9 + 5, nmax = 5e5 + 2;

struct segm {
  int l = inf, r = 0;
  segm operator ++() {
    r++;
    l++;
    return *this; 
  }
  segm operator |(const segm& x) const { return segm{min(l, x.l), max(r, x.r)}; }
  segm operator |=(const segm& x) { return (*this = *this | x); }
  bool operator ==(const int& x) const { return l <= x && x <= r; }
};
int A[nmax * 2], B[nmax * 2];
segm atrA[nmax * 2], atrB[nmax * 2];


void decompose(int poz, int target, int type) {
  if(poz == 0)
    return;
  int val = (type == 0? A[poz] : B[poz]), ch = (type == 0? 'A' : 'B');
  if(A[poz - 1] <= val && atrA[poz - 1] == target)
    decompose(poz - 1, target - 1, 0);
  else
    decompose(poz - 1, target,  1);
  cout << (char)ch;
};

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= 2 * n; i++) cin >> A[i];
  for(int i = 1; i <= 2 * n; i++) cin >> B[i];
  A[0] = B[0] = -1;
  atrA[0] = segm{0, 0};
  atrB[0] = segm{0, 0};
  for(int i = 1; i <= 2 * n; i++) {
    if(A[i] >= A[i - 1]) atrA[i] |= atrA[i - 1];
    if(A[i] >= B[i - 1]) atrA[i] |= atrB[i - 1];
    if(B[i] >= A[i - 1]) atrB[i] |= atrA[i - 1];
    if(B[i] >= B[i - 1]) atrB[i] |= atrB[i - 1];
    ++atrA[i];
    
    int mn = min(A[i - 1], B[i - 1]);
    if(A[i] < mn)
      A[i] = inf;
     if(B[i] < mn)
      B[i] = inf;
    //cerr << A[i] << '\t' << B[i] << '\n' << atrA[i].l << ' ' << atrA[i].r << ", " << atrB[i].l << ' ' << atrB[i].r << '\n';
  }
  
  if(atrA[2 * n] == n)
    decompose(2 * n, n - 1, 0);
  else if(atrB[2 * n] == n)
    decompose(2 * n, n, 1);
  else
    cout << "-1";
  cout << '\n';
  return 0;
}

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