Submission #1322486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322486		simona1230	Event Hopping (BOI22_events)	C++20	0 / 100	175 ms	4540 KiB

events

#include<bits/stdc++.h>
using namespace std;

struct help
{
    int l,r,i;
    help(){}
    help(int _l,int _r,int _i)
    {
        l=_l;
        r=_r;
        i=_i;
    }
};

int n,q;
help a[100001],b[100001];

void read()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
        a[i].i=i;
    }

    for(int i=1;i<=q;i++)
    {
        cin>>b[i].l>>b[i].r;
        b[i].i=i;
    }
}

bool cmpr(help h1,help h2)
{
    return h1.r<h2.r;
}

int c[200001];
int p[200001];

void solve()
{
    sort(a+1,a+n+1,cmpr);
    for(int i=1;i<=n;i++)
    {
        p[a[i].i]=i;
        c[i]=i;
    }

    for(int i=1;i<n;i++)
    {
        if(a[i+1].l<=a[i].r&&a[i].r<=a[i+1].r)
        {
            c[i+1]=c[i];
        }
    }

    for(int i=1;i<=q;i++)
    {
        int x=b[i].l,y=b[i].r;
        x=p[x];
        y=p[y];

        if(a[x].r==a[y].r)
        {
            cout<<1<<endl;
        }
        else if(a[x].r>a[y].r||c[x]!=c[y])
        {
            cout<<"impossible"<<endl;
        }
        else
        {
            cout<<y-x<<endl;
        }
    }
}

int main()
{
    read();
    solve();
    return 0;
}
/*
6
5
8 9
5 8
9 12
1 3
2 3
10 13
1 3
2 5
1 6
4 5
3 4
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30