제출 #1109479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109479		Pekiban	Passport (JOI23_passport)	C++17	100 / 100	1611 ms	149488 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 L[N], R[N], ans[N][2];
void resiretarda(int x) {
    for (int i = 1; i <= C; ++i) {
        g[i].clear();
    }
    C = n;
    build();
    for (int i = 1; i <= n; ++i)    Add(L[i], R[i], i);
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    fill(di, di+C+1, 1e9);
    fill(vis, vis+C+1, 0);
    fill(ri, ri+C+1, 0);
    for (int i = 1; i <= n; ++i) {
        if (L[i] == 1) {
            ri[i] = R[i], di[i] = 1;
            pq.push({1, -ri[i], i});
        }
    }
    while (!pq.empty()) {
        auto [D, RIII, 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;
            }
            if (di[u] == di[s] + w) {
                ri[u] = max({ri[u], -RIII, Ri});
                pq.push({di[u], -ri[u], u});
            }
        }
    }
    multiset<long long> ms, vs;
    for (int i = 1; i <= n; ++i)    ms.insert(R[i]);
    fill(f, f+n+1, 1e9);
    f[n] = 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--;
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans[i][x] = di[i] + f[ri[i]];
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> L[i] >> R[i];
    }
    resiretarda(0);
    for (int i = 1; i <= n; ++i) {
        int X = L[i];
        L[i] = n+1-R[i], R[i] = n+1-X;
    }
    reverse(L+1, L+n+1);
    reverse(R+1, R+n+1);
    resiretarda(1);
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (min(ans[x][0], ans[n-x+1][1]) > 5e5 ? -1 : min(ans[x][0], ans[n-x+1][1])) << '\n';
    }
}

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