Submission #1317034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317034		JahonaliX	Passport (JOI23_passport)	C++20	100 / 100	447 ms	90536 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define int long long
constexpr int mod = 1e9 + 7, inf = 1e17;

struct segment_tree {
    int n;
    vector<vector<int>> a;
    vector<int> id, val;
    void build(int v = 1, int l = 0, int r = -1) {
        if (r < 0) r += n;
        if (l == r) id[l] = v, val[v] = l;
        else {
            int m = (l + r) >> 1;
            build(v << 1, l, m);
            build(v << 1 | 1, m + 1, r);
        }
    }
    segment_tree(int m) { n = m, a.assign(n << 2, {}), id.assign(n, 0), val.assign(n << 2, -1), build(); }
    void update(int L, int R, int x, int v = 1, int l = 0, int r = -1) {
        if (r < 0) r += n;
        if (L <= l && r <= R) a[v].emplace_back(id[x]);
        else {
            int m = (l + r) >> 1;
            if (L <= m) update(L, R, x, v << 1, l, m);
            if (R > m) update(L, R, x, v << 1 | 1, m + 1, r);
        }
    }
    vector<int> answer() {
        vector<int> dp(n << 2, inf), dpl = dp, dpr = dp, ret(n, -1);
        dpl[id[0]] = 0;
        priority_queue<pair<int, int>> q;
        q.emplace(0, id[0]);
        while (!q.empty()) {
            auto [w, i] = q.top();
            q.pop();
            if (i > 1 && dpl[i / 2] > -w) dpl[i / 2] = -w, q.emplace(w, i / 2);
            for (int j : a[i]) {
                if (dpl[j] < -w + 2) continue;
                dpl[j] = -w + 1;
                q.emplace(w - 1, j);
            }
        }
        dpr[id[n - 1]] = 0;
        q.emplace(0, id[n - 1]);
        while (!q.empty()) {
            auto [w, i] = q.top();
            q.pop();
            if (i > 1 && dpr[i / 2] > -w) dpr[i / 2] = -w, q.emplace(w, i / 2);
            for (int j : a[i]) {
                if (dpr[j] < -w + 2) continue;
                dpr[j] = -w + 1;
                q.emplace(w - 1, j);
            }
        }
        for (int i = 1; i < (n << 2); ++i) {
            if (val[i] == -1) continue;
            dp[i] = min(inf, dpl[i] + dpr[i] + 1 - (val[i] != 0) - (val[i] != n - 1)), q.emplace(-dp[i], i);
        }
        while (!q.empty()) {
            auto [w, i] = q.top();
            q.pop();
            if (i > 1 && dp[i / 2] > -w) dp[i / 2] = -w, q.emplace(w, i / 2);
            for (int j : a[i]) {
                if (dp[j] < -w + 2) continue;
                dp[j] = -w + 1;
                q.emplace(w - 1, j);
            }
        }
        for (int i = 1; i < (n << 2); ++i) {
            if (dp[i] == inf || val[i] == -1) continue;
            ret[val[i]] = dp[i];
        }
        return ret;
    }
};

int32_t main() {
#ifdef JahonaliX
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; ++i) cin >> l[i] >> r[i], l[i]--, r[i]--;
    segment_tree s(n);
    for (int i = 0; i < n; ++i) s.update(l[i], r[i], i);
    auto dp = s.answer();
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        x--;
        cout << dp[x] << '\n';
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46