oj.uz

Submission #1069658

# Submission time Handle Problem Language Result Execution time Memory
1069658 2024-08-22T07:49:44 Z 정희우(#11134) Passport (JOI23_passport) C++17
6 / 100
 383 ms 87324 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=200010;

int n,q;
int la[MAX_N],ra[MAX_N];
int vi[MAX_N<<2];
vint edge[MAX_N<<2][2];
int dt[MAX_N<<2];
int seg[MAX_N<<2];
vint bfs[MAX_N];

void init_edge(int i,int s,int e)
{
    vi[i]=(s+1==e) ? s : i+n;
    if(i>1)
        edge[vi[i]][0].push_back(vi[i>>1]);
    if(s+1==e)return;
    init_edge(i<<1,s,(s+e)>>1);
    init_edge(i<<1|1,(s+e)>>1,e);
}

void update_edge(int i,int s,int e,int l,int r,int v)
{
    if(s>=r || e<=l)return;
    if(l<=s && e<=r)
    {
        edge[vi[i]][1].push_back(v);
        return;
    }
    update_edge(i<<1,s,(s+e)>>1,l,r,v);
    update_edge(i<<1|1,(s+e)>>1,e,l,r,v);
}

void init_seg(int i,int s,int e)
{
    seg[i]=MAX_N;
    if(s+1==e)return;
    init_seg(i<<1,s,(s+e)>>1);
    init_seg(i<<1|1,(s+e)>>1,e);
}

void update_(int i,int s,int e,int x,int v)
{
    if(s>x || e<=x)return;
    if(s==x && x+1==e)
    {
        seg[i]=v;
        return;
    }
    update_(i<<1,s,(s+e)>>1,x,v);
    update_(i<<1|1,(s+e)>>1,e,x,v);
    seg[i]=min(seg[i<<1],seg[i<<1|1]);
}

int find_(int i,int s,int e,int l,int r)
{
    if(s>=r || e<=l)return MAX_N;
    if(l<=s && e<=r)return seg[i];
    return min(find_(i<<1,s,(s+e)>>1,l,r),find_(i<<1|1,(s+e)>>1,e,l,r));
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    init_edge(1,0,n);
    for(int i=0;i<n;i++)
    {
        cin >> la[i] >> ra[i];
        la[i]--;
        update_edge(1,0,n,la[i],ra[i],i);
    }
    fill(dt,dt+(MAX_N<<2),MAX_N);
    fill(dt,dt+n,1);
    init_seg(1,0,n);
    update_(1,0,n,0,1);
    for(int i=1;i<n;i++)
    {
        int v;
        if(la[i]==0)v=0;
        else v=find_(1,0,n,la[i],ra[i]);
        dt[i]+=v;
        update_(1,0,n,i,v+1);
    }
    init_seg(1,0,n);
    update_(1,0,n,n-1,1);
    for(int i=n-2;i>=0;i--)
    {
        int v;
        if(ra[i]==n)v=0;
        else v=find_(1,0,n,la[i],ra[i]);
        dt[i]+=v;
        update_(1,0,n,i,v+1);
    }
    for(int i=0;i<n;i++)
        if(dt[i]<MAX_N)bfs[dt[i]].push_back(i);
    for(int d=0;d<n;d++)
    {
        while(!bfs[d].empty())
        {
            int p=bfs[d].back();
            bfs[d].pop_back();
            for(auto v : edge[p][0])
                if(dt[v]>d)
                {
                    dt[v]=d;
                    bfs[d].push_back(v);
                }
            for(auto v : edge[p][1])
                if(dt[v]>d+1)
                {
                    dt[v]=d+1;
                    bfs[d+1].push_back(v);
                }
        }
    }
    cin >> q;
    while(q--)
    {
        int i;
        cin >> i;i--;
        cout << (dt[i]>=MAX_N ? -1 : dt[i]) << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49756 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 383 ms 87324 KB Output is correct
5 Correct 226 ms 77648 KB Output is correct
6 Correct 194 ms 77348 KB Output is correct
7 Correct 96 ms 69576 KB Output is correct
8 Correct 83 ms 65104 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49752 KB Output is correct
2 Correct 8 ms 49888 KB Output is correct
3 Correct 8 ms 49752 KB Output is correct
4 Correct 8 ms 49752 KB Output is correct
5 Correct 7 ms 49756 KB Output is correct
6 Correct 7 ms 49644 KB Output is correct
7 Correct 7 ms 50008 KB Output is correct
8 Correct 8 ms 49888 KB Output is correct
9 Correct 8 ms 49756 KB Output is correct
10 Incorrect 7 ms 49756 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49752 KB Output is correct
2 Correct 8 ms 49888 KB Output is correct
3 Correct 8 ms 49752 KB Output is correct
4 Correct 8 ms 49752 KB Output is correct
5 Correct 7 ms 49756 KB Output is correct
6 Correct 7 ms 49644 KB Output is correct
7 Correct 7 ms 50008 KB Output is correct
8 Correct 8 ms 49888 KB Output is correct
9 Correct 8 ms 49756 KB Output is correct
10 Incorrect 7 ms 49756 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49752 KB Output is correct
2 Correct 8 ms 49888 KB Output is correct
3 Correct 8 ms 49752 KB Output is correct
4 Correct 8 ms 49752 KB Output is correct
5 Correct 7 ms 49756 KB Output is correct
6 Correct 7 ms 49644 KB Output is correct
7 Correct 7 ms 50008 KB Output is correct
8 Correct 8 ms 49888 KB Output is correct
9 Correct 8 ms 49756 KB Output is correct
10 Incorrect 7 ms 49756 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49756 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 383 ms 87324 KB Output is correct
5 Correct 226 ms 77648 KB Output is correct
6 Correct 194 ms 77348 KB Output is correct
7 Correct 96 ms 69576 KB Output is correct
8 Correct 83 ms 65104 KB Output is correct
9 Correct 8 ms 49752 KB Output is correct
10 Correct 8 ms 49888 KB Output is correct
11 Correct 8 ms 49752 KB Output is correct
12 Correct 8 ms 49752 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49644 KB Output is correct
15 Correct 7 ms 50008 KB Output is correct
16 Correct 8 ms 49888 KB Output is correct
17 Correct 8 ms 49756 KB Output is correct
18 Incorrect 7 ms 49756 KB Output isn't correct
19 Halted 0 ms 0 KB -