Submission #1308168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308168		thnhann	Passport (JOI23_passport)	C++20	100 / 100	1279 ms	139196 KiB

passport

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=2e5;
const int inf =1e18;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

int n, q;
ii range[nmax + 5];

vector<ii> adj[nmax * 5 + 5];
int L[nmax * 5 + 5];
int R[nmax * 5 + 5];
int ans[nmax * 5 + 5];
int get_id(int id) {
    return n + id;
}
void build(int id, int l, int r) {
    int u = get_id(id);
    if (l == r) {
        adj[l].pb({u,0});
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    adj[get_id(id * 2)].pb({u,0});
    adj[get_id(id * 2 + 1)].pb({u,0});
}

void add_edges(int id, int l, int r, int u, int v, int country) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        adj[get_id(id)].pb({country,1});
        return;
    }
    int mid = (l + r) >> 1;
    add_edges(id * 2, l, mid, u, v, country);
    add_edges(id * 2 + 1, mid + 1, r, u, v, country);
}

void dijk(int dist[], vector<int>& seeds) {
    for(int i=1;i<=n*5;i++) dist[i] = inf;
    priority_queue<ii, vector<ii>, greater<ii>> pq;

    for(int u : seeds) {
        if (u <= n) dist[u] = 1;
        else dist[u] = 0;
        pq.push({dist[u], u});
    }

    while(!pq.empty()) {
        int d = pq.top().fi;
        int u = pq.top().se;
        pq.pop();

        if (d > dist[u]) continue;

        for(auto v : adj[u]) {
            if (dist[v.fi] > dist[u] + v.se) {
                dist[v.fi] = dist[u] + v.se;
                pq.push({dist[v.fi], v.fi});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        cin >> range[i].fi >> range[i].se;
        add_edges(1, 1, n, range[i].fi, range[i].se, i);
    }
    vector<int>candidate;
    for(int i = 1; i <= n; i++) {
        if(range[i].fi == 1) candidate.pb(i);
    }
    dijk(L,candidate);

    candidate.clear();

    for(int i = 1; i <= n; i++) {
        if(range[i].se == n) candidate.pb(i);
    }
    dijk(R,candidate);
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for(int i=1;i<=n*5;i++)
        ans[i] = inf;

    for(int i = 1; i <= n; i++) {
        if(L[i] != inf && R[i] != inf) {
            ans[i] = L[i] + R[i] - 1;
            pq.push({ans[i], i});
        }
    }

    while(!pq.empty()) {
        int d = pq.top().fi;
        int u = pq.top().se;
        pq.pop();

        if (d > ans[u]) continue;

        for(auto v : adj[u]) {
            if (ans[v.fi] > ans[u] + v.se) {
                ans[v.fi] = ans[u] + v.se;
                pq.push({ans[v.fi], v.fi});
            }
        }
    }

    int query;

    cin >> query;
    while(query--) {
        int x;
        cin >> x;
        if(ans[x] >= inf) cout << -1;
        else cout << ans[x];
        el;
    }

}
//Can i get a kiss? And can u make it last forever?;

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