Submission #1370452

#TimeUsernameProblemLanguageResultExecution timeMemory
1370452pirmyratgPassport (JOI23_passport)C++20
100 / 100
463 ms82836 KiB
#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define SZ(s) (int)s.size()

const int N = 200005;
const int INF = 1e9;

int n, q;
int l[N], r[N], pos[N];
int f[4 * N], gr[4 * N], dp[4 * N];
vector <pair <int, int>> g[4 * N];

void build(int nd, int l, int r) {
    if(l == r) {
        pos[l] = nd;
        return;
    }
    int md = (l + r) / 2;
    build(nd * 2, l, md);
    build(nd * 2 + 1, md + 1, r);
    g[nd * 2].pb({nd, 0});
    g[nd * 2 + 1].pb({nd, 0});
}

void add(int nd, int l, int r, int ql, int qr, int k, int w) {
    if(r < ql or qr < l) return;
    if(ql <= l and r <= qr) {
        g[nd].pb({pos[k], w});
        return;
    }
    int md = (l + r) / 2;
    add(nd * 2, l, md, ql, qr, k, w);
    add(nd * 2 + 1, md + 1, r, ql, qr, k, w);
}

void dijkstra(int s, int d[]) {
    for(int i = 0; i < 4 * N; i++) d[i] = INF;
    set <pair <int, int>> st;
    d[s] = 0;
    st.insert({0, s});
    while(SZ(st)) {
        int v = st.begin()->ss;
        st.erase(st.begin());
        for(auto &edge : g[v]) {
            int u = edge.ff;
            int w = edge.ss;
            if(d[u] > d[v] + w) {
                if(st.find({d[u], u}) != st.end()) st.erase({d[u], u});
                d[u] = d[v] + w;
                st.insert({d[u], u});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }

    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        add(1, 1, n, l[i], r[i], i, 1);
    }

    dijkstra(pos[1], f);
    dijkstra(pos[n], gr);

    for(int i = 0; i < 4 * N; i++) dp[i] = INF;
    set <pair <int, int>> st;

    for(int i = 1; i <= n; i++) {
        int u = pos[i];
        if(f[u] == INF or gr[u] == INF) continue;
        dp[u] = f[u] + gr[u] - (i != 1 and i != n);
        st.insert({dp[u], u});
    }

    while(SZ(st)) {
        int v = st.begin()->ss;
        st.erase(st.begin());
        for(auto &edge : g[v]) {
            int u = edge.ff;
            int w = edge.ss;
            if(dp[u] > dp[v] + w) {
                if(st.find({dp[u], u}) != st.end()) st.erase({dp[u], u});
                dp[u] = dp[v] + w;
                st.insert({dp[u], u});
            }
        }
    }

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

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...