Submission #961259

#	Time	Username	Problem	Language	Result	Execution time	Memory
961259		anton	Passport (JOI23_passport)	C++17	0 / 100	0 ms	348 KiB

passport

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define int long long

const int MAX_N =2500;
const int INF=  1e9;
pii inter[MAX_N];

struct minTree{
    vector<int> tr;
    int sz= 1;
    minTree(int len){
        while(sz<len){
            sz*=2;
        }
        tr.resize(2*sz, INF);
    }

    int get(int l, int r){
        //cout<<l<<" "<<r<<endl;
        l +=sz;
        r+=sz+1;
        int res= 1e18;

        for(; l<r; l/=2, r/=2){
            if(l%2 ==1){
                res= min(res, tr[l++]);
            }
            if(r%2 == 1){
                res = min(res, tr[--r]);
            }
        }
        return res;
    }
    void set(int id, int val){
        id+=sz;
        tr[id] = val;
        for(int i = id/2; i>=1; i/=2){
            tr[i] = min(tr[i*2], tr[i*2+1]);
        }
    }

};

int dist[MAX_N][MAX_N];
int n;

void BFS(int id){
    queue<pii> q;
    dist[id][id] = 0;
    q.push({id, 0});

    while(q.size()>0){
        int cur= q.front().first;
        int cur_dist = q.front().second;
        //cout<<cur<<" "<<cur_dist<<endl;
        q.pop();
        for(int i = inter[cur].first; i<=inter[cur].second; i++){
            if(dist[id][i] == INF){
                dist[id][i]  = cur_dist+1;
                q.push({i, cur_dist+1});
            }
        }
    }
    
}

void precalc_dist(){
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++)dist[i][j] = INF;
        BFS(i);
    }
}
signed main(){
    cin>>n;

    for(int i = 0; i<n; i++){
        cin>>inter[i].first>>inter[i].second;
        inter[i].first--;
        inter[i].second--;
    }

    minTree dpr(n);
    dpr.set(n-1,0);
    for(int i = n-2; i>=0; i--){
        int best=  dpr.get(i+1, inter[i].second);
        if(inter[i].second == n-1){
            best= 0;
        }
        //cout<<best+1<<" ";
        dpr.set(i, best+1);
    }

    minTree dpl(n);
    dpl.set(0, 0);

    for(int i = 1; i<n; i++){
        int best = dpl.get(inter[i].first, i-1);
        if(inter[i].first == 0){
            best= 0;
        }
        dpl.set(i, best+1);
    }

    int q;
    cin>>q;
    precalc_dist();

    for(int i = 0; i<q; i++){
        int v;
        cin>>v;
        v--;
        int res= INF;
        for(int j = 0; j<n; j++){
            //cout<<dist[v][j]<<end
            if(dpr.tr[j+dpr.sz]-1 + dpl.tr[j+dpl.sz] + dist[v][j]<res){
                //cout<<v<<" "<<j<<endl;
                //cout<<dpr.tr[j+dpr.sz]<<" "<<dpl.tr[j+dpl.sz]<<" "<<dist[v][j]<<endl;
            }
            res= min(res, dpr.tr[j+dpr.sz]-1 + dpl.tr[j+dpl.sz] + dist[v][j]);
            
        }
        if(res==INF){
            cout<<-1<<endl;
        }
        else{
            cout<<res<<endl;
        }
    }
}

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