Submission #1109446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109446		Pekiban	Passport (JOI23_passport)	C++17	46 / 100	592 ms	102692 KiB

passport

#include <bits/stdc++.h>

using namespace std;

const int N = 8e5+5;
vector<array<int, 3>> g[N];
bool vis[N];
int di[N], ri[N], lc[N], rc[N], n, C;
long long f[N];
void add(int u, int v, int x, int R = -1) {
    g[u].push_back({v, x, R});
}
int build(int l = 1, int r = n) {
    if (l == r) return l;
    int m = (l+r)/2, nd = ++C;
    lc[nd] = build(l, m);
    rc[nd] = build(m+1, r);
    add(lc[nd], nd, 0);
    add(rc[nd], nd, 0);
    return nd;
}
void Add(int l, int r, int u, int i = n+1, int l2 = 1, int r2 = n) {
    if (l <= l2 && r2 <= r) {
        add(i, u, 1, r);
        return;
    } 
    int m2 = (l2 + r2)/2;
    if (l <= m2)    Add(l, r, u, lc[i], l2, m2);
    if (m2+1 <= r)  Add(l, r, u, rc[i], m2+1, r2);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n; C = n;
    int L[n+1], R[n+1];
    build();
    for (int i = 1; i <= n; ++i) {
        cin >> L[i] >> R[i];
        Add(L[i], R[i], i);
    }
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
    fill(di, di+C+1, 1e9);
    for (int i = 1; i <= n; ++i) {
        if (L[i] == 1) {
            ri[i] = R[i], di[i] = 1;
            pq.push({1, i});
        }
    }
    while (!pq.empty()) {
        auto [D, s] = pq.top(); pq.pop();
        if (vis[s]) continue;
        vis[s] = 1;
        for (auto [u, w, Ri] : g[s]) {
            if (di[u] > di[s] + w) {
                di[u] = di[s] + w;
                pq.push({di[u], u});
            }
            if (di[u] == di[s] + w) ri[u] = max({ri[u], ri[s], Ri});
        }
    }
    multiset<int> ms, vs;
    for (int i = 1; i <= n; ++i)    ms.insert(R[i]);
    fill(f, f+n+1, 1e9);
    f[n] = 0;
    vs.insert(0);
    for (int i = n; i >= 1; --i) {
        if (i != n) {
            f[i] = (vs.empty() ? 1e9 : *vs.begin()) +1;
            vs.insert(f[i]);
        }
        if (i == 1) continue;
        int RRR = *ms.rbegin();
        ms.erase(ms.find(R[i]));
        while (RRR != *ms.rbegin()) {
            vs.erase(vs.find(f[RRR]));
            RRR--;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (di[x] + f[ri[x]] > 5e5 ? -1 : di[x] + f[ri[x]]) << '\n';
    }
}

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