Submission #915300

#	Time	Username	Problem	Language	Result	Execution time	Memory
915300		minhnhatnoe	Passport (JOI23_passport)	C++17	6 / 100	172 ms	99652 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LG = 20;

vector<pair<int, int>> a[20], b[20];

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    a[0].resize(n), b[0].resize(n);
    for (int i=0; i<n; i++){
        cin >> a[0][i].first >> b[0][i].first;
        a[0][i].first--, b[0][i].first--;
        a[0][i].second = b[0][i].second = i;
    }

    for (int i=1; i<LG; i++){
        a[i].resize(n), b[i].resize(n);
        for (int j1=0, j2=1<<(i-1); j2<n; j1++, j2++){
            a[i][j1] = min(a[i-1][j1], a[i-1][j2]);
            b[i][j1] = max(b[i-1][j1], b[i-1][j2]);
        }
    }

    const int XX = 0;
    const int XY = XX + n;
    const int YX = XY + n;
    const int YY = YX + n;
    const int SIZE = YY + 1;

    vector<vector<pair<int, bool>>> g(SIZE);
    for (int i=0; i<n; i++){
        int l = a[0][i].first, r = b[0][i].first;
        int lg = 31 - __builtin_clz(r - l + 1);
        if (b[0][i].first == n-1){
            g[XY+i].emplace_back(XX+i, 0);
            g[YY].emplace_back(YX+i, 0);
        }
        else{
            int mxpos = max(b[lg][l], b[lg][r - (1 << lg) + 1]).second;
            g[XX+mxpos].emplace_back(XX+i, 1);
            g[XY+mxpos].emplace_back(XY+i, 1);
            g[YX+mxpos].emplace_back(YX+i, 1);
        }

        if (a[0][i].first == 0){
            g[YX+i].emplace_back(XX+i, 0);
            g[YY].emplace_back(XY+i, 0);
        }
        else{
            int mnpos = min(a[lg][l], a[lg][r - (1 << lg) + 1]).second;
            g[XX+mnpos].emplace_back(XX+i, 1);
            g[XY+mnpos].emplace_back(XY+i, 1);
            g[YX+mnpos].emplace_back(YX+i, 1);
        }
    }

    vector<int> dist(SIZE, INT_MAX);
    dist[YY] = 0;
    for (deque<int> q = {YY}; q.size();){
        int v = q.front(); q.pop_front();
        for (const pair<int, bool> &e: g[v]){
            if (dist[v] + e.second < dist[e.first]){
                dist[e.first] = dist[v] + e.second;
                if (e.second) q.push_back(e.first);
                else q.push_front(e.first);
            }
        }
    }

    int q; cin >> q;
    while (q--){
        int x; cin >> x; x--;
        if (dist[x] == INT_MAX) cout << "-1\n";
        else cout << dist[x]+1 << "\n";
    }
}

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