제출 #1304659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304659		vlomaczk	Passport (JOI23_passport)	C++20	22 / 100	102 ms	29288 KiB

passport

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

ll inf = 1e18;

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

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

    void upd(ll x, pair<ll,ll> 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<ll,ll> query(ll a, ll b) {
        if(a == b) return {-Tree[a+base].second, Tree[a+base].first};
        a += base-1;
        b += base+1;
        pair<ll,ll> 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<ll,ll>> Tree;
    ll base;

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

    void upd(ll x, pair<ll,ll> 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<ll,ll> query(ll a, ll b) {
        if(a == b) return {Tree[a+base].first, -Tree[a+base].second};
        a += base-1;
        b += base+1;
        pair<ll,ll> 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);

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

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

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

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

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

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

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

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

            pair<ll,ll> 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