Submission #889198

#	Time	Username	Problem	Language	Result	Execution time	Memory
889198		12345678	Passport (JOI23_passport)	C++17	6 / 100	942 ms	154524 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5;
ll n, l[nx], r[nx], q, x;
vector<pair<ll, ll>> d[nx];
vector<ll> vs(nx), st(nx, 1e9), ed(nx, 1e9), ans(nx, 1e9);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

void build(int l, int r, int i)
{
    if (l==r) return void(d[l].push_back({i+n, 0}));
    int md=(l+r)/2;
    d[2*i+n].push_back({i+n, 0});
    d[2*i+n+1].push_back({i+n, 0});
    build(l, md, 2*i);
    build(md+1, r, 2*i+1);
}

void update(int l, int r, int i, int ql, int qr, int idx)
{
    if (ql<=l&&r<=qr) return void(d[i+n].push_back({idx, 1}));
    if (r<ql||qr<l) return;
    int md=(l+r)/2;
    update(l, md, 2*i, ql, qr, idx);
    update(md+1, r, 2*i+1, ql, qr, idx);
}

void dijk(int st, vector<ll> &res)
{
    for (int i=0; i<nx; i++) vs[i]=0;
    pq.push({0, st});
    res[st]=0;
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        vs[u]=1;
        for (auto [v, w]:d[u]) if (!vs[v]&&cw+w<res[v]) res[v]=cw+w, pq.push({cw+w, v});
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    build(1, n, 1);
    for (int i=1; i<=n; i++) cin>>l[i]>>r[i], update(1, n, 1, l[i], r[i], i);
    dijk(1, st);
    dijk(n, ed);
    for (int i=1; i<nx; i++) vs[i]=0;
    for (int i=1; i<nx; i++) if ((ans[i]=st[i]+ed[i])<1e9) pq.push({ans[i], i});
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        vs[u]=1;
        for (auto [v, w]:d[u]) if (!vs[v]&&cw+w<ans[v]) ans[v]=cw+w, pq.push({cw+w, v});
    }
    cin>>q;
    while (q--) cin>>x, cout<<(ans[x]>=1e9?-1:ans[x])<<'\n';
}

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