Submission #1242951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242951		Hamed_Ghaffari	Passport (JOI23_passport)	C++20	100 / 100	1368 ms	74012 KiB

passport

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 2e5+5, inf=1e7;

int n, L[MXN], R[MXN], N;
vector<pii> g[MXN*3];

int dis[2][MXN*3], val[MXN];

void bfs(int id, int v) {
    fill(dis[id]+1, dis[id]+N+1, inf);
    deque<int> q;
    dis[id][v] = 0;
    q.push_back(v);
    while(!q.empty()) {
        int v = q.front();
        q.pop_front();
        for(auto [u, w] : g[v])
            if(dis[id][u]>dis[id][v]+w) {
                dis[id][u] = dis[id][v]+w;
                if(w) q.push_back(u);
                else q.push_front(u);
            }
    }
}

int D[MXN*3];

void SP() {
    vector<int> vec(n);
    iota(vec.begin(), vec.end(), 1);
    sort(vec.begin(), vec.end(), [&](int u, int v) {
        return val[u] > val[v];
    });
    fill(D+1, D+N+1, inf);
    deque<int> q;
    while(!q.empty() || !vec.empty()) {
        if(q.empty())
            while(!vec.empty()) {
                int dd = val[vec.back()];
                if(dd<D[vec.back()]) {
                    D[vec.back()] = dd;
                    q.push_back(vec.back());
                    vec.pop_back();
                    break;
                }
                vec.pop_back();
            }
        if(q.empty()) break;
        while(!vec.empty()) {
            int dd = val[vec.back()];
            if(dd<D[vec.back()] && dd<=D[q.front()]+1) {
                D[vec.back()] = dd;
                q.push_back(vec.back());
                vec.pop_back();
            }
            else break;
        }
        int v = q.front();
        q.pop_front();
        for(auto [u, w] : g[v])
            if(D[u]>D[v]+w) {
                D[u] = D[v]+w;
                if(w) q.push_back(u);
                else q.push_front(u);
            }
    }
}

int name[MXN<<2], mn[2][MXN<<2];

int build(int l=1, int r=n+1, int id=1) {
    if(r-l == 1) return name[id] = l;
    name[id] = ++N;
    g[build(l, mid, lc)].push_back({name[id], 0});
    g[build(mid, r, rc)].push_back({name[id], 0});
    return name[id];
}

void build2(int l=1, int r=n+1, int id=1) {
    if(r-l == 1) {
        mn[0][id] = dis[0][l];
        mn[1][id] = dis[1][l];
        return;
    }
    build2(l, mid, lc);
    build2(mid, r, rc);
    mn[0][id] = min(mn[0][lc], mn[0][rc]);
    mn[1][id] = min(mn[1][lc], mn[1][rc]);
}

void add(int s, int e, int v, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        g[name[id]].push_back({v, 1});
        return;
    }
    add(s, e, v, l, mid, lc);
    add(s, e, v, mid, r, rc);
}

inline pii min_(pii x, pii y) {
    return pii(min(x.X, y.X), min(x.Y, y.Y));
}

pii get(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e) return {inf, inf};
    if(s<=l && r<=e) return {mn[0][id], mn[1][id]};
    return min_(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    N = n;
    build();
    for(int i=1; i<=n; i++) {
        cin >> L[i] >> R[i];
        add(L[i], R[i]+1, i);
    }
    bfs(0, 1);
    bfs(1, n);
    build2();
    for(int i=1; i<=n; i++) {
        pii x = get(L[i], R[i]+1);
        val[i] = x.X+x.Y+1;
    }
    SP();
    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        cout << (D[x]>=inf ? -1 : D[x]) << '\n';
    }
    return 0;
}

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