Submission #1300441

#TimeUsernameProblemLanguageResultExecution timeMemory
1300441Francisco_MartinPassport (JOI23_passport)C++20
100 / 100
868 ms132356 KiB
//JOISC 2023D1-C Passport
//https://oj.uz/problem/view/JOI23_passport

#include <bits/stdc++.h>
using namespace std;
#define fastIO cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
const ll MAXN = 1e6;

vpll g[MAXN]; vll to(MAXN); ll sz;

void build(ll n){
    sz=1; while(sz<n) sz*=2;
    for(int i=1; i<2*sz-1; i++) g[i].push_back({(i-1)/2,0});
    for(int i=0; i<n; i++) to[i]=sz-1+i;
}

void add(ll v,ll l,ll r,ll x=0,ll lx=0,ll rx=sz){
    if(r<=lx || rx<=l) return;
    if(l<=lx && rx<=r){
        g[x].push_back({to[v],1});
        return;
    }
    ll m=(lx+rx)/2;
    add(v,l,r,2*x+1,lx,m); add(v,l,r,2*x+2,m,rx);
}

int main(){
    ll n, l, r, q;
    cin >> n; build(n);
    for(int i=0; i<n; i++){
        cin >> l >> r; add(i,l-1,r);
    }
    auto dijkstra=[&](ll a,vll &dis){
        priority_queue<pll,vpll,greater<pll>> pq;
        pq.push({0,a}); dis[a]=0;
        while(!pq.empty()){
            auto [w,v]=pq.top(); pq.pop();
            if(dis[v]!=w) continue;
            for(auto [u,w2]:g[v]) if(dis[u]>w+w2){
                dis[u]=w+w2; pq.push({w+w2,u});
            }
        }
    };
    vll dis1(2*sz,1e18), dis2=dis1, dis3=dis1;
    dijkstra(to[0],dis1); dijkstra(to[n-1],dis2); dis1[to[0]]=dis2[to[n-1]]=1;
    for(int i=0; i<n; i++) g[2*sz-1].push_back({to[i],dis1[to[i]]+dis2[to[i]]});
    dijkstra(2*sz-1,dis3);
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> l; l--;
        cout << (dis3[to[l]]>=1e18?-1:dis3[to[l]]-1) << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...