Submission #1188374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188374		TsotneSV	Passport (JOI23_passport)	C++20	100 / 100	513 ms	90520 KiB

passport

#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5; 
const ll inf=1e8,INF=1e18; 

vector<pii> G[4*MAXN];
vi d[3];
int n,q,L[MAXN],R[MAXN],lab[MAXN];

void build(int v,int tl,int tr) {
    
    if(tl == tr) {
        lab[tl] = v;
        return;
    }

    int tm = (tl + tr)/2;

    build(2*v,tl,tm); build(2*v+1,tm+1,tr);

    G[2*v].pb({v,0}); G[2*v+1].pb({v,0});
}

void add(int v,int tl,int tr,int l,int r,int idx) {
    if(l > r) return;
    if(tl == l and tr == r) {
        G[v].pb({idx,1});
    } else {
        int tm = (tl + tr)/2;
        add(2*v,tl,tm,l,min(r,tm),idx);
        add(2*v+1,tm+1,tr,max(l,tm+1),r,idx);
    }
}

void trav(int t) {

    set<pii> s; 

    for(int i=1;i<=4*n;i++) {
        if(d[t][i] < 1e6) s.ins({d[t][i],i});
    }

    while(s.size()) {
        auto [w,u] = *(s.begin()); s.erase(s.begin());
        if(d[t][u] != w) continue;
        for(auto [k,we] : G[u]) {
            if(we + w < d[t][k]) {
                d[t][k] = we + w;
                s.ins({d[t][k],k});
            }
        }
    }

}

void solve(int tc = 0){
    cin>>n;

    for(int j=0;j<3;j++) d[j] = vi(4*MAXN,inf);

    build(1,1,n);

    for(int i=1;i<=n;i++) {
        cin>>L[i]>>R[i];
       // if(L[i] == 1) d[0][lab[i]] = 0;
       // if(R[i] == n) d[1][lab[i]] = 0;
        add(1,1,n,L[i],R[i],lab[i]);
    } d[0][lab[1]] = d[1][lab[n]] = 0;

    trav(0); trav(1); 
    
    for(int i=1;i<=n;i++) d[2][lab[i]] = d[0][lab[i]] + d[1][lab[i]] - (i != 1 and i != n);

    trav(2);

  //  debug(d[0][lab[5]]);
    
    cin>>q;

    while(q--) {
        int x; cin>>x; x=lab[x];
        print(d[2][x] > 1e6 ? -1 : d[2][x]);
    }

}

signed main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    int tc=1;
    //cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

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