Submission #991913

#	Time	Username	Problem	Language	Result	Execution time	Memory
991913		onbert	Passport (JOI23_passport)	C++17	40 / 100	2098 ms	32480 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 20, INF = 1e9;
int Rcost[maxn];
pair<int,int> Lcost[maxn];
bool cmp(int a, int b) {
    return Lcost[a].second < Lcost[b].second;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    pair<int,int> a[n+1];
    vector<pair<int,int>> Lpos[n+1], Rpos[n+1];
    for (int i=1;i<=n;i++) {
        cin >> a[i].first >> a[i].second;
        if (i!=1) Lpos[a[i].first].push_back({a[i].second, i});
        if (i!=n) Rpos[a[i].second].push_back({a[i].first, i});
    }


    for (int i=1;i<=n;i++) sort(Rpos[i].rbegin(), Rpos[i].rend());
    set<int> s;
    for (int i=1;i<=n;i++) if (Rpos[i].size()>0) s.insert(i);
    vector<int> from = {n}, to;
    int Rcost[n+1];
    for (int i=1;i<=n;i++) Rcost[i] = INF;
    for (int cost=-1; from.size()>0; cost++) {
        for (int u:from) Rcost[u] = max(cost, (int)0);
        for (int u:from) {
            vector<int> del;
            if (s.size()==0) break;
            for (auto r = s.rbegin(); ;r++) {
                int R = *r;
                if (R<u) break;
                while (Rpos[R].size()>0 && Rpos[R].back().first<=u) {
                    to.push_back(Rpos[R].back().second);
                    Rpos[R].pop_back();
                }
                if (Rpos[R].size()==0) del.push_back(R);
                if (*r == *s.begin()) break;
            }
            for (int i:del) s.erase(i);
        }
        from.clear();
        swap(to, from);
    }

    for (int i=1;i<=n;i++) sort(Lpos[i].begin(), Lpos[i].end());
    for (int i=1;i<=n;i++) if (Lpos[i].size()>0) s.insert(i);
    from = {1};
    for (int i=1;i<=n;i++) Lcost[i] = {INF, INF};
    Lcost[1].second = Rcost[1] + 1;
    for (int cost=0; from.size()>0; cost++) {
        sort(from.begin(), from.end(), cmp);
        for (int u:from) Lcost[u].first = cost;
        for (int u:from) {
            vector<int> del;
            for (int L:s) {
                if (L>u) break;
                while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
                    int v = Lpos[L].back().second;
                    to.push_back(v);
                    Lcost[v].second = min(Rcost[v], Lcost[u].second);
                    Lpos[L].pop_back();
                }
                if (Lpos[L].size()==0) del.push_back(L);
            }
            for (int i:del) s.erase(i);
        }
        from.clear();
        swap(to, from);
    }
    
    int q;
    cin >> q;
    for (int i=0;i<q;i++) {
        int pos;
        cin >> pos;
        if (Lcost[pos].first>=INF || Lcost[pos].second>=INF) cout << "-1\n";
        else cout << Lcost[pos].first + Lcost[pos].second << "\n";
    }
}

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