Submission #1304656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304656		vlomaczk	Passport (JOI23_passport)	C++20	22 / 100	96 ms	19532 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(false);
    cin.tie(nullptr);

    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--;

        const int MAXN = 1000; // > n
        unordered_map<long long,int> dist;
        auto encode = [&](int a,int b){ return (long long)a*MAXN+b; };

        queue<pair<int,int>> Q;
        Q.push({x,x});
        dist[encode(x,x)] = 0;

        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}) {
                long long key = encode(c,d);
                if(!dist.count(key)) {
                    dist[key] = dist[encode(a,b)] + 1;
                    Q.push({c,d});
                }
            }
        }

        long long goalKey = encode(0,n-1);
        if(dist.count(goalKey)) cout << dist[goalKey] << "\n";
        else cout << "-1\n";
    }

    return 0;
}

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