Submission #65934811

---

Source Code Expand

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define all(x) x.begin(), x.end()
#define ca(x) for(auto i:x) cout<<i<<" ";
#define nl cout<<"\n";
#define f first 
#define s second

using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n; cin>>n;
    int l[n], r[n]; ll ar[n];
    for(int i=0; i<n; i++) cin>>ar[i];
    for(int i=0; i<n; i++) cin>>l[i]>>r[i], l[i]--, r[i]--;
    int q; cin>>q;
    auto does_intersect = [&](int i, int j) -> bool {
        if(l[i] > r[j] || l[j] > r[i]) return 0;
        return 1;
    };
    vector<ll> best_end(2*n,1e16);
    vector<ll> best_start(2*n,1e16);
    for(int i=0; i<n; i++) {
        best_end[r[i]] = min(best_end[r[i]], ar[i]);
        best_start[l[i]] = min(best_start[l[i]], ar[i]);
    }
    for(int i=1; i<2*n; i++) {
        best_end[i] = min(best_end[i], best_end[i-1]);
        best_start[2*n-i-1] = min(best_start[2*n-i-1], best_start[2*n-i]);
    }

    auto get_best_start = [&](int i) -> ll { 
        if(i+1 >= 2*n) return 1e16;
        return best_start[i+1];
    };
    auto get_best_end = [&](int i) -> ll { 
        if(i-1 < 0) return 1e16;
        return best_end[i-1];
    };
    while(q--){
        int a, b;
        cin>>a>>b; a--; b--;
        if(!does_intersect(a,b)) {
            cout<<ar[a]+ar[b]<<"\n";
        } else {
            ll res = 1e16;
            res = min(res, ar[a]+ar[b]+get_best_start(r[a])+get_best_end(l[b]));
            res = min(res, ar[a]+ar[b]+get_best_start(r[b])+get_best_end(l[a]));
            res = min(res, ar[a]+ar[b]+get_best_start(max(r[b],r[a])));
            res = min(res, ar[a]+ar[b]+get_best_end(min(l[b],l[a])));
            if(res == 1e16) cout<<-1<<"\n";
            else cout<<res<<"\n";
        }
    }

}

Submission Info

Judge Result