Submission #1192351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192351		adhityamv	Passport (JOI23_passport)	C++20	6 / 100	530 ms	97060 KiB

passport

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=1000000;
//const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << "," << p.se << " ";
}
void solve(){
    int n;
    cin >> n;
    int l[n];
    int r[n];
    for(int i=0;i<n;i++){
        cin >> l[i] >> r[i];
        l[i]--,r[i]--;
    }
    vector<pii> edges[2*n];
    for(int i=n-1;i>0;i--){
        edges[2*i].push_back(mp(i,0));
        edges[2*i+1].push_back(mp(i,0));
    }
    for(int i=0;i<n;i++){
        int li=l[i]+n;
        int ri=r[i]+n+1;
        //cout << li << " " << ri << "?\n";
        while(li<ri){
            if(li&1){
                //cout << li << " " << i+n << "\n";
                edges[li].push_back(mp(i+n,1));
                li++;
            }
            if(ri&1){
                ri--;
                edges[ri].push_back(mp(i+n,1));
                //cout << ri << " " << i+n << "\n";
            }
            li>>=1;
            ri>>=1;
        }
    }
    int dist1[2*n];
    int distn[2*n];
    for(int i=0;i<2*n;i++){
        dist1[i]=distn[i]=INF;
    }
    {   
        dist1[n]=0;
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        pq.push(mp(dist1[n],n));
        while(!pq.empty()){
            auto [w,u]=pq.top();
            pq.pop();
            if(w!=dist1[u]) continue;
            for(auto [v,w1]:edges[u]){
                if(dist1[v]>w+w1){
                    dist1[v]=w+w1;
                    pq.push(mp(dist1[v],v));
                }
            }
        }
    }
    for(int i=0;i<2*n;i++){
        if(dist1[i]==0) dist1[i]++;
        //cout << dist1[i] << "\n";
    }
    {
        distn[2*n-1]=0;
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        pq.push(mp(distn[2*n-1],2*n-1));
        while(!pq.empty()){
            auto [w,u]=pq.top();
            pq.pop();
            if(w!=distn[u]) continue;
            for(auto [v,w1]:edges[u]){
                if(distn[v]>w+w1){
                    distn[v]=w+w1;
                    pq.push(mp(distn[v],v));
                }
            }
        }
        distn[2*n-1]++;
    }
    for(int i=0;i<2*n;i++){
        if(distn[i]==0) distn[i]++;
        //cout << distn[i] << "\n";
    }
    int dist1n[2*n];
    for(int i=0;i<2*n;i++){
        dist1n[i]=dist1[i]+distn[i]-1;
        //cout << dist1n[i] << "?\n";
    }
    {
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        for(int i=n;i<2*n;i++){
            pq.push(mp(dist1n[i],i));
        }
        while(!pq.empty()){
            auto [w,u]=pq.top();
            pq.pop();
            if(w!=dist1n[u]) continue;
            for(auto [v,w1]:edges[u]){
                if(dist1n[v]>w+w1){
                    dist1n[v]=w+w1;
                    pq.push(mp(dist1n[v],v));
                }
            }
        }
    }
    int q;
    cin >> q;
    while(q--){
        int i;
        cin >> i;
        i--;
        if(dist1n[i+n]>=INF-1){
            cout << -1 << "\n";
        } else cout << dist1n[i+n] << "\n";
    }
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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