Submission #63099329

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e9 + 1;

struct SegTree {
    vector<int> t;
    int n;

    SegTree (vector<int> a) {
        n = a.size();
        t.resize(2 * n);
        for (int i = 0; i < n; i++) t[i + n] = a[i];
        for (int i = n - 1; i > 0; i--) t[i] = min(t[i << 1], t[i << 1 | 1]);
    }

    int query(int l, int r) {
        int res = MAX;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = min(res, t[l++]);
            if (r & 1) res = min(res, t[--r]);
        }
        return res;
    }
};

int main() {
    int n;
    cin >> n;

    vector<int> w(n);
    for (int i = 0; i < n; i++) cin >> w[i];

    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];

    vector<int> ir(n), il(n);
    iota(ir.begin(), ir.end(), 0);
    iota(il.begin(), il.end(), 0);

    sort(ir.begin(), ir.end(), [&](int i, int j) { return r[i] < r[j]; });
    sort(il.begin(), il.end(), [&](int i, int j) { return l[i] < l[j]; });

    vector<int> wr(n), wl(n);
    for (int i = 0; i < n; i++) wr[i] = w[ir[i]];
    for (int i = 0; i < n; i++) wl[i] = w[il[i]];

    SegTree tr(wr), tl(wl);

    int q;
    cin >> q;

    while (q--) {
        int s, t;
        cin >> s >> t;
        s--; t--;

        if (r[s] - l[s] < r[t] - l[t]) swap(s, t);

        bool pos = false;
        long long res = 0;
        res += w[t];
        res += w[s];

        if (r[s] < l[t] || r[t] < l[s]) {
            pos = true;
        } else {
            int mn = MAX;

            mn = min(mn, tr.query(0, lower_bound(ir.begin(), ir.end(), min(l[s], l[t]), [&](int i, int v) {
                return r[i] < v;
            }) - ir.begin()));

            mn = min(mn, tl.query(lower_bound(il.begin(), il.end(), max(r[s], r[t]), [&](int i, int v) {
                return l[i] <= v;
            }) - il.begin(), n));

            if (l[t] <= r[s] && r[s] <= r[t]) swap(s, t);

            if (l[t] <= l[s] && l[s] <= r[t]) {
                int mn1 = tr.query(0, lower_bound(ir.begin(), ir.end(), l[s], [&](int i, int v) {
                    return r[i] < v;
                }) - ir.begin());

                int mn2 = tl.query(lower_bound(il.begin(), il.end(), r[t], [&](int i, int v) {
                    return l[i] <= v;
                }) - il.begin(), n);

                if (mn1 != MAX && mn2 != MAX) {
                    mn = min(mn, mn1 + mn2);
                }
            }

            if (mn != MAX) {
                pos = true;
                res += mn;
            }
        }

        if (pos) cout << res << "\n";
        else cout << -1 << "\n";
    }

    return 0;
}

Submission Info

Judge Result