Submission #1257397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257397		notisora	Passport (JOI23_passport)	C++20	100 / 100	452 ms	48324 KiB

passport

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long

using namespace std;

const int INF=1e8;
const int N=2e5+5;
vector<int>st[N*4];
int n,q;
int ans[N];
pair<int,int>Passport[N];
bool vis[N];
bool visst[N*4];

void update(int u,int v,int val,int node=1,int l=1,int r=n){
    if (u>r || l>v) return;
    if (u<=l && r<=v){
        st[node].pb(val);
        return;
    }
    int m=(l+r)>>1;
    update(u,v,val,node*2,l,m);
    update(u,v,val,node*2+1,m+1,r);
}

void dijkstra(vector<int>&d){

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n*4;i++) visst[i]=0;

    for(int i=1;i<=n;i++){
        if (d[i]>=INF) continue;
        pq.push({d[i],i});
    }

    while(!pq.empty()){
        int dis=pq.top().fi;
        int pos=pq.top().se;
        pq.pop();
        if (vis[pos]) continue;
        vis[pos]=1;

        int node=1,l=1,r=n;
        while(16032008){
            if (!visst[node]){
                visst[node]=1;
                for(int&u:st[node]){
                    if (d[u]>dis+1){
//                        cout<<pos<<" "<<u<<el;
                        d[u]=dis+1;
                        pq.push({d[u],u});
                    }
                }
            }
            if (l==r) break;
            int m=(l+r)>>1;
            if (pos<=m){
                node=node*2;
                r=m;
            }
            else{
                node=node*2+1;
                l=m+1;
            }
//            cout<<el;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("i.INP","r",stdin);
    cin>>n;
    vector<int>dL(n+1,INF),dR(n+1,INF),dp(n+1,INF);

    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        Passport[i]={l,r};
        update(l,r,i);
    }

    dL[1]=0;
    dR[n]=0;

    dijkstra(dL);
    dijkstra(dR);

    for(int i=1;i<=n;i++){
        dp[i]=dL[i]+dR[i];
        if (i>1 && i<n) dp[i]--;
        if (Passport[i].fi==1 && Passport[i].se==n) dp[i]=1;
    }
    dijkstra(dp);

    int q;
    cin>>q;
    while(q--){
        int z;
        cin>>z;
        if (dp[z]>n*2) cout<<-1;
        else cout<<dp[z];
        cout<<el;
    }
}

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