Submission #1257383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257383		notisora	Passport (JOI23_passport)	C++20	0 / 100	9 ms	19012 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 N=2e5+5;
vector<int>st[N*4];
int n,q;
int ans[N];

struct Passport{
    int l,r,idx;
    bool operator < (const Passport&other) const{
        if (l==other.l) return r<other.r;
        return l<other.l;
    }
};
Passport arr[N];

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;
    vector<bool>visst(n*4+5,0);
    vector<bool>vis(n+5,0);
    for(int i=1;i<=n;i++){
        if (d[i]>=1e8) 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;
        if (dis>d[pos]) continue;

        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){
                        d[u]=dis+1;
                        pq.push({d[u],u});
                    }
                }
            }
            if (l==r) break;
            int m=(l+r)>>1;
            if (pos<=m){
                node*=2;
                r=m;
            }
            else{
                node=node*2+1;
                l=m+1;
            }
        }
    }
}

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,1e8),dR(n+1,1e8),dp(n+1,1e8);

    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        arr[i]={l,r,i};
        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]-1;
        if (arr[i].l==1 && arr[i].r==n) dp[i]=1;
    }
    dijkstra(dp);

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

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