oj.uz

Submission #967772

# Submission time Handle Problem Language Result Execution time Memory
967772 2024-04-22T19:33:33 Z maxFedorchuk Event Hopping (BOI22_events) C++17
0 / 100
 164 ms 37200 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10;
const long long INF=1e9;

pair < int , int > tree[4*MX];
void upd(int v,int tl,int tr,int in,pair < int , int > zn)
{
    if(tl==tr)
    {
        tree[v]=min(tree[v],zn);
        return;
    }

    int mid=(tl+tr)/2;
    if(in<=mid)
    {
        upd(v*2,tl,mid,in,zn);
    }
    else
    {
        upd(v*2+1,mid+1,tr,in,zn);
    }

    tree[v]=min(tree[v*2],tree[v*2+1]);
}
pair < int , int > fget(int v,int tl,int tr,int l,int r)
{
    if(r<tl || tr<l)
    {
        return make_pair(INF,0);
    }

    if(l<=tl && tr<=r)
    {
        return tree[v];
    }

    int mid=(tl+tr)/2;
    return min(fget(v*2,tl,mid,l,r),fget(v*2+1,mid+1,tr,l,r));
}

int l[MX],r[MX];
int n,k;

void compr()
{
    map < int , int > mp;

    for(int i=1;i<=n;i++)
    {
        mp[l[i]]=1;
        mp[r[i]]=1;
    }

    int uk=0;
    for(auto & u:mp)
    {
        uk++;
        u.second=uk;
    }

    for(int i=1;i<=n;i++)
    {
        l[i]=mp[l[i]];
        r[i]=mp[r[i]];
    }
}

int lca[20][MX];
void fun(int a,int b)
{
    if(a==b)
    {
        cout<<"0\n";
        return;
    }

    if(l[b]<=r[a] && r[a]<=r[b])
    {
        cout<<"1\n";
        return;
    }

    if(r[b]<r[a] || r[a]<l[lca[19][b]])
    {
        cout<<"imposible\n";
        return;
    }

    int ans=2;
    for(int i=19;i>=0;i--)
    {
        if(r[a]<l[lca[i][b]])
        {
            b=lca[i][b];
            ans+=(1<<i);
        }
    }

    cout<<ans<<"\n";
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>k;

    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
    }
    compr();

    fill(tree+1,tree+4*MX,make_pair(INF,0));
    for(int i=1;i<=n;i++)
    {
        upd(1,1,2*n,r[i],make_pair(l[i],i));
    }

    for(int i=1;i<=n;i++)
    {
        lca[0][i]=fget(1,1,2*n,l[i],r[i]).second;
    }
    for(int i=1;i<20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            lca[i][j]=lca[i-1][lca[i-1][j]];
        }
    }

    for(int i=1;i<=k;i++)
    {
        int a,b;
        cin>>a>>b;

        fun(a,b);
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 23644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 23644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 23644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 23644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 32164 KB Output is correct
2 Correct 164 ms 32392 KB Output is correct
3 Correct 155 ms 32300 KB Output is correct
4 Incorrect 147 ms 37200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 23644 KB Output isn't correct
2 Halted 0 ms 0 KB -