Submission #915031

#	Time	Username	Problem	Language	Result	Execution time	Memory
915031		Tuanlinh123	Building 4 (JOI20_building4)	C++17	100 / 100	217 ms	68920 KiB

building4

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=1000005;
ll a[maxn], b[maxn];
pll va[maxn], vb[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=1; i<=n*2; i++) cin >> a[i], va[i]={-1, -1};
    for (ll i=1; i<=n*2; i++) cin >> b[i], vb[i]={-1, -1};
    va[0]={0, 0}, vb[0]={0, 0};
    auto merge=[&](pll a, pll b, ll inc)
    {
        if (b.fi==-1) return a;
        if (a.fi==-1) return mp(b.fi+inc, b.se+inc);
        return mp(min(a.fi, b.fi+inc), max(a.se, b.se+inc));
    };
    for (ll i=1; i<=n*2; i++)
    {
        if (a[i-1]<=a[i]) va[i]=merge(va[i], va[i-1], 0);
        if (a[i-1]<=b[i]) vb[i]=merge(vb[i], va[i-1], 1);
        if (b[i-1]<=a[i]) va[i]=merge(va[i], vb[i-1], 0);
        if (b[i-1]<=b[i]) vb[i]=merge(vb[i], vb[i-1], 1);
    }
    vector <char> ans;
    for (ll crr=n, i=n*2, val=1e9; i; i--)
    {
        if (va[i].fi<=crr && crr<=va[i].se && a[i]<=val)
            ans.pb('A'), val=a[i];
        else if (vb[i].fi<=crr && crr<=vb[i].se && b[i]<=val)
            ans.pb('B'), val=b[i], crr--;
        else {cout << "-1"; exit(0);}
    }
    reverse(ans.begin(), ans.end());
    for (char i:ans) cout << i;
}

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