Submission #1304655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304655		vlomaczk	Passport (JOI23_passport)	C++20	0 / 100	535 ms	1114112 KiB

passport

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

int inf = 1e9;

struct TreeMax {
    vector<pair<int,int>> Tree;
    int base;

    TreeMax(int n) {
        base = 1;
        while(base < n) base *= 2;
        Tree.assign(2*base, {-inf,-inf});
    }

    void upd(int x, pair<int,int> val) {
        x += base;
        Tree[x] = {val.second, -val.first};
        x /= 2;
        while(x > 0) {
            Tree[x] = max(Tree[x+x], Tree[x+x+1]);
            x /= 2;
        }
    }

    pair<int,int> query(int a, int b) {
        if(a == b) return {-Tree[a+base].second, Tree[a+base].first};
        a += base-1;
        b += base+1;
        pair<int,int> ans = {-inf,-inf};
        while(a/2 != b/2) {
            if(a%2==0) ans = max(ans, Tree[a+1]);
            if(b%2==1) ans = max(ans, Tree[b-1]);
            a /= 2; b /= 2;
        }
        return {-ans.second, ans.first};
    }
};

struct TreeMin {
    vector<pair<int,int>> Tree;
    int base;

    TreeMin(int n) {
        base = 1;
        while(base < n) base *= 2;
        Tree.assign(2*base, {inf,inf});
    }

    void upd(int x, pair<int,int> val) {
        x += base;
        Tree[x] = {val.first, -val.second};
        x /= 2;
        while(x > 0) {
            Tree[x] = min(Tree[x+x], Tree[x+x+1]);
            x /= 2;
        }
    }

    pair<int,int> query(int a, int b) {
        if(a == b) return {Tree[a+base].first, -Tree[a+base].second};
        a += base-1;
        b += base+1;
        pair<int,int> ans = {inf,inf};
        while(a/2 != b/2) {
            if(a%2==0) ans = min(ans, Tree[a+1]);
            if(b%2==1) ans = min(ans, Tree[b-1]);
            a /= 2; b /= 2;
        }
        return {ans.first, -ans.second};
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for(int i=0;i<n;i++) {
        cin >> l[i] >> r[i];
        l[i]--; r[i]--;
    }

    TreeMin left(n);
    TreeMax right(n);

    for(int i=0;i<n;i++) {
        left.upd(i, {l[i], r[i]});
        right.upd(i, {l[i], r[i]});
    }

    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        x--;

        vector<vector<int>> dist(n+1, vector<int>(n+1, inf));
        queue<pair<int,int>> Q;
        dist[x][x] = 0;
        Q.push({x,x});

        while(!Q.empty()) {
            auto [a,b] = Q.front(); Q.pop();

            pair<int,int> L = left.query(a,b);
            L.first = min(L.first, a);
            L.second = max(L.second, b);

            pair<int,int> R = right.query(a,b);
            R.first = min(R.first, a);
            R.second = max(R.second, b);

            for(auto [c,d] : {L,R}) {
                if(dist[c][d] == inf) {
                    dist[c][d] = dist[a][b] + 1;
                    Q.push({c,d});
                }
            }
        }

        if(dist[0][n-1] == inf) cout << "-1\n";
        else cout << dist[0][n-1] << "\n";
    }

    return 0;
}

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