Submission #967773

#	Time	Username	Problem	Language	Result	Execution time	Memory
967773		maxFedorchuk	Event Hopping (BOI22_events)	C++17	100 / 100	240 ms	37356 KiB

events

#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<<"impossible\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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30