Submission #799878

#	Time	Username	Problem	Language	Result	Execution time	Memory
799878		phoenix	Passport (JOI23_passport)	C++17	100 / 100	1633 ms	154996 KiB

passport

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;
const int M = (1 << 18);
vector<pair<int, int>> g[3 * M];

void build(int l = 0, int r = M - 1, int v = 1) {
    if(l == r) {
        g[l].push_back({v + M, 0});
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * v);
    build(mid + 1, r, 2 * v + 1);
    g[2 * v + M].push_back({v + M, 0});
    g[2 * v + M + 1].push_back({v + M, 0});
}

void add(int ql, int qr, int u, int l = 0, int r = M - 1, int v = 1) {
    if(qr < l || ql > r) 
        return;
    if(ql <= l && r <= qr) {
        g[v + M].push_back({u, 1});
        return;
    }
    int mid = (l + r) / 2;
    add(ql, qr, u, l, mid, 2 * v);
    add(ql, qr, u, mid + 1, r, 2 * v + 1); 
}

int n;
vector<ll> dijkstra(vector<pair<int, ll>> start) {
    vector<ll> dist(3 * M, INF + 10);
    for(auto [i, d] : start) dist[i] = d;
    set<pair<ll, int>> st;
    for(int i = 0; i < (int)dist.size(); i++) 
        st.insert({dist[i], i});
    while(!st.empty()) {
        int s = st.begin()->second;
        st.erase(st.begin());
        for(auto [to, w] : g[s]) {
            if(dist[to] > dist[s] + w) {
                st.erase({dist[to], to});
                dist[to] = dist[s] + w;
                st.insert({dist[to], to});
            }
        }
    }
    vector<ll> res(n + 1);
    for(int i = 1; i <= n; i++)
        res[i] = dist[i];
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    build();
    cin >> n;
    int l[n + 1], r[n + 1];
    for(int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        add(l[i], r[i], i);
    }
    auto A = dijkstra({{1, 0}});
    auto B = dijkstra({{n, 0}});
    // for(int i = 1; i <= n; i++) 
    //     cout << A[i] << ' ';
    // cout << '\n';
    // for(int i = 1; i <= n; i++) 
    //     cout << B[i] << ' ';
    // cout << '\n';
    vector<pair<int, ll>> C;
    for(int i = 1; i <= n; i++) 
        C.push_back({i, A[i] + B[i] - (1 < i && i < n)});
    auto F = dijkstra(C);
    // for(int i = 1; i <= n; i++) 
    //     cout << F[i] << ' ';
    // cout << '\n';

    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        if(F[x] >= INF) cout << -1 << '\n';
        else cout << F[x] << '\n';
    }
}

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