Submission #943676

#	Time	Username	Problem	Language	Result	Execution time	Memory
943676		andrei_boaca	Passport (JOI23_passport)	C++17	48 / 100	2055 ms	175444 KiB

passport

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,L[200005],R[200005],torgt[200005],tolft[200005],sufL[200005],prefR[200005],sol[200005];
pii d1[200005],dn[200005];
set<int> arb[4*200005];
vector<int> nodes;
void build(int nod,int st,int dr)
{
    arb[nod].clear();
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int a,int b, int val)
{
    if(st>=a&&dr<=b)
    {
        if(val>0)
            arb[nod].insert(val);
        else
            arb[nod].erase(-val);
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
}
void query(int nod,int st,int dr,int poz)
{
    for(int j:arb[nod])
        nodes.push_back(j);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(poz<=mij)
        query(nod*2,st,mij,poz);
    else
        query(nod*2+1,mij+1,dr,poz);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>L[i]>>R[i];
    for(int i=1;i<=n;i++)
        prefR[i]=max(prefR[i-1],R[i]);
    sufL[n+1]=1e9;
    for(int i=n;i>=1;i--)
        sufL[i]=min(sufL[i+1],L[i]);
    torgt[n]=0;
    for(int i=n-1;i>=1;i--)
    {
        if(prefR[i]<=i)
            torgt[i]=-1;
        else
        {
            int j=prefR[i];
            if(torgt[j]==-1)
                torgt[i]=-1;
            else
                torgt[i]=1+torgt[j];
        }
    }
    tolft[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(sufL[i]>=i)
            tolft[i]=-1;
        else
        {
            int j=sufL[i];
            if(tolft[j]==-1)
                tolft[i]=-1;
            else
                tolft[i]=1+tolft[j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        d1[i]={-1,0};
        dn[i]={-1,0};
    }
    d1[1]={0,1};
    build(1,1,n);
    for(int i=2;i<=n;i++)
        update(1,1,n,L[i],R[i],i);
    set<pair<pii,int>> coada;
    coada.insert({{0,1},1});
    while(!coada.empty())
    {
        int val=(*coada.begin()).first.first;
        auto it=prev(coada.lower_bound({{val+1,0},0}));
        int nod=(*it).second;
        coada.erase(it);
        nodes.clear();
        query(1,1,n,nod);
        for(int j:nodes)
        {
            d1[j].first=d1[nod].first+1;
            d1[j].second=max(d1[nod].second,R[j]);
            update(1,1,n,L[j],R[j],-j);
            coada.insert({d1[j],j});
        }
    }
    dn[n]={0,n};
    build(1,1,n);
    for(int i=1;i<n;i++)
        update(1,1,n,L[i],R[i],i);
    coada.insert({{0,n},n});
    while(!coada.empty())
    {
        auto it=coada.begin();
        int nod=(*it).second;
        coada.erase(it);
        nodes.clear();
        query(1,1,n,nod);
        for(int j:nodes)
        {
            dn[j].first=dn[nod].first+1;
            dn[j].second=min(dn[nod].second,L[j]);
            update(1,1,n,L[j],R[j],-j);
            coada.insert({dn[j],j});
        }
    }
    for(int i=1;i<=n;i++)
    {
        sol[i]=1e9;
        if(d1[i].first!=-1)
        {
            int poz=d1[i].second;
            if(torgt[poz]!=-1)
                sol[i]=min(sol[i],d1[i].first+torgt[poz]);
        }
        if(dn[i].first!=-1)
        {
            int poz=dn[i].second;
            if(tolft[poz]!=-1)
                sol[i]=min(sol[i],dn[i].first+tolft[poz]);
        }
        if(sol[i]>n)
            sol[i]=-1;
    }
    int q;
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        cout<<sol[x]<<'\n';
    }
    return 0;
}

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