Submission #1262264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262264		erering	Passport (JOI23_passport)	C++20	100 / 100	845 ms	172032 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=2e5+5,inf=1e18;
int n;
pair<int,int> p[N];
vector<pair<int,int>> rev[N*4];
int offset=1,sol[N*4][3];
void build(int node,int lo,int hi){
    if(lo==hi)return;
    rev[node*2].pb({node,0});
    rev[node*2+1].pb({node,0});
    int mid=(lo+hi)/2;
    build(node*2,lo,mid);
    build(node*2+1,mid+1,hi);
}
void query(int node,int qlo,int qhi,int lo,int hi,int id){
    if(lo>=qlo && hi<=qhi){
        rev[node].pb({id,1});
        return;
    }
    if(lo>qhi || hi<qlo)return;
    int mid=(lo+hi)/2;
    query(node*2,qlo,qhi,lo,mid,id);
    query(node*2+1,qlo,qhi,mid+1,hi,id);
}
void solve(int type,int start){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=0;i<N*4;i++){
        pq.push({sol[i][type],i});
    }
    while(!pq.empty()){
        int score=pq.top().first,node=pq.top().second;
       // if(type==1)cout<<score<<' '<<node<<endl;
        pq.pop();
        if(sol[node][type]<score)continue;
        for(auto i:rev[node]){
            int x=i.first;
            if(sol[x][type]>score+i.second){
                pq.push({score+i.second,x});
                sol[x][type]=score+i.second;
            }
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<3;i++){
        for(int j=0;j<N*4;j++)sol[j][i]=inf;
    }
    cin>>n;
    while(offset<=n)offset*=2;
    build(1,0,offset-1);
    for(int i=1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
        if(p[i].first==1)sol[i+offset][0]=0;
        if(p[i].second==n)sol[i+offset][1]=0;
        query(1,p[i].first,p[i].second,0,offset-1,i+offset);
    }
    solve(0,1+offset);
    solve(1,n+offset);
    for(int i=1;i<=n;i++)sol[i+offset][2]=sol[i+offset][0]+sol[i+offset][1]+1;
   // cout<<sol[1+offset][1]<<endl;
    solve(2,313);
    int q; cin>>q;
    while(q--){
        int x; cin>>x; x+=offset;
        cout<<(sol[x][2]>n?-1:sol[x][2])<<endl;
    }
}

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