oj.uz

Submission #943694

# Submission time Handle Problem Language Result Execution time Memory
943694 2024-03-11T18:08:34 Z andrei_boaca Passport (JOI23_passport) C++17
100 / 100
 478 ms 63116 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
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];
vector<int> arb[4*200005];
int total=0;
vector<int> nodes;
bool use[200005];
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)
    {
        arb[nod].push_back(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])
    {
        if(!use[j])
            nodes.push_back(j);
    }
    arb[nod].clear();
    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;
        use[nod]=1;
        coada.erase(it);
        nodes.clear();
        query(1,1,n,nod);
        for(int j:nodes)
        {
            use[j]=1;
            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);
    for(int i=1;i<=n;i++)
        use[i]=0;
    coada.insert({{0,n},n});
    while(!coada.empty())
    {
        auto it=coada.begin();
        int nod=(*it).second;
        use[nod]=1;
        coada.erase(it);
        nodes.clear();
        query(1,1,n,nod);
        for(int j:nodes)
        {
            use[j]=1;
            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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 444 ms 58848 KB Output is correct
5 Correct 212 ms 40788 KB Output is correct
6 Correct 120 ms 40788 KB Output is correct
7 Correct 139 ms 43344 KB Output is correct
8 Correct 90 ms 39716 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 5 ms 24920 KB Output is correct
6 Correct 5 ms 24924 KB Output is correct
7 Correct 5 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 5 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 25136 KB Output is correct
12 Correct 6 ms 25044 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 6 ms 24924 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 5 ms 24920 KB Output is correct
6 Correct 5 ms 24924 KB Output is correct
7 Correct 5 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 5 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 25136 KB Output is correct
12 Correct 6 ms 25044 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 6 ms 24924 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct
16 Correct 8 ms 25180 KB Output is correct
17 Correct 8 ms 25040 KB Output is correct
18 Correct 7 ms 25180 KB Output is correct
19 Correct 10 ms 25284 KB Output is correct
20 Correct 6 ms 25200 KB Output is correct
21 Correct 7 ms 25180 KB Output is correct
22 Correct 6 ms 25180 KB Output is correct
23 Correct 7 ms 25180 KB Output is correct
24 Correct 7 ms 25352 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 5 ms 24924 KB Output is correct
5 Correct 5 ms 24920 KB Output is correct
6 Correct 5 ms 24924 KB Output is correct
7 Correct 5 ms 24924 KB Output is correct
8 Correct 5 ms 24924 KB Output is correct
9 Correct 5 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 25136 KB Output is correct
12 Correct 6 ms 25044 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 6 ms 24924 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct
16 Correct 8 ms 25180 KB Output is correct
17 Correct 8 ms 25040 KB Output is correct
18 Correct 7 ms 25180 KB Output is correct
19 Correct 10 ms 25284 KB Output is correct
20 Correct 6 ms 25200 KB Output is correct
21 Correct 7 ms 25180 KB Output is correct
22 Correct 6 ms 25180 KB Output is correct
23 Correct 7 ms 25180 KB Output is correct
24 Correct 7 ms 25352 KB Output is correct
25 Correct 5 ms 24924 KB Output is correct
26 Correct 5 ms 25028 KB Output is correct
27 Correct 8 ms 25180 KB Output is correct
28 Correct 10 ms 25088 KB Output is correct
29 Correct 7 ms 25180 KB Output is correct
30 Correct 7 ms 25180 KB Output is correct
31 Correct 7 ms 25180 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 444 ms 58848 KB Output is correct
5 Correct 212 ms 40788 KB Output is correct
6 Correct 120 ms 40788 KB Output is correct
7 Correct 139 ms 43344 KB Output is correct
8 Correct 90 ms 39716 KB Output is correct
9 Correct 5 ms 24924 KB Output is correct
10 Correct 5 ms 24920 KB Output is correct
11 Correct 5 ms 24924 KB Output is correct
12 Correct 5 ms 24924 KB Output is correct
13 Correct 5 ms 24920 KB Output is correct
14 Correct 5 ms 24924 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct
16 Correct 5 ms 24924 KB Output is correct
17 Correct 5 ms 24924 KB Output is correct
18 Correct 5 ms 24924 KB Output is correct
19 Correct 5 ms 25136 KB Output is correct
20 Correct 6 ms 25044 KB Output is correct
21 Correct 5 ms 24924 KB Output is correct
22 Correct 6 ms 24924 KB Output is correct
23 Correct 5 ms 24924 KB Output is correct
24 Correct 8 ms 25180 KB Output is correct
25 Correct 8 ms 25040 KB Output is correct
26 Correct 7 ms 25180 KB Output is correct
27 Correct 10 ms 25284 KB Output is correct
28 Correct 6 ms 25200 KB Output is correct
29 Correct 7 ms 25180 KB Output is correct
30 Correct 6 ms 25180 KB Output is correct
31 Correct 7 ms 25180 KB Output is correct
32 Correct 7 ms 25352 KB Output is correct
33 Correct 5 ms 24924 KB Output is correct
34 Correct 5 ms 25028 KB Output is correct
35 Correct 8 ms 25180 KB Output is correct
36 Correct 10 ms 25088 KB Output is correct
37 Correct 7 ms 25180 KB Output is correct
38 Correct 7 ms 25180 KB Output is correct
39 Correct 7 ms 25180 KB Output is correct
40 Correct 478 ms 63116 KB Output is correct
41 Correct 237 ms 43348 KB Output is correct
42 Correct 281 ms 53180 KB Output is correct
43 Correct 278 ms 58172 KB Output is correct
44 Correct 142 ms 43352 KB Output is correct
45 Correct 161 ms 44112 KB Output is correct
46 Correct 81 ms 33400 KB Output is correct
47 Correct 247 ms 50772 KB Output is correct
48 Correct 272 ms 50996 KB Output is correct