Submission #1125018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125018		EfeBabagil	Event Hopping (BOI22_events)	C++20	0 / 100	1595 ms	2628 KiB

events

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

int32_t main()
{
    int n,q;
    cin>>n>>q;
    vector<array<int,3>> events(n);
    for(int i=0;i<n;i++)
    {
        int e,s;
        cin>>s>>e;
        events[i]={s,e,i};
    }
    sort(events.begin(),events.end());
    
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        if(a==b)
        {
            cout<<"0"<<endl;
            continue;
        }
        for(int i=0;i<n;i++)
        {
            if(events[i][2]==a){
            a=i;
            break;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(events[i][2]==b){
            b=i;
            break;
            }
        }
        /*
        for(int i=0;i<n;i++)
        {
            if(i==a)
            cout<<"a:";
            if(i==b)
            cout<<"b:";
            cout<<events[i][0]<<" "<<events[i][1]<<" "<<events[i][2]<<endl;
        }*/
        int cnt=0;
        int flag=0;
        int j=a;
        int ae=events[a][1];
        int as=events[a][0];
        int mx=ae;
        int mxi=-1;
        while(1)
        {
            int temp=0;
            for(int i=0;i<=n;i++)
            {
                if(mx>=events[i][0]&&events[i][0]>=as)
                {
                    if(i==b)
                    {
                        cout<<cnt+1<<endl;
                        flag=1;
                        break;
                    }
                    if(events[i][1]>mx)
                    {
                        temp=max(temp,events[i][1]);
                    }
                }
            }
            if(flag)
            {
                break;
            }
            if(temp>mx)
            {
                cnt++;
                mx=temp;
                //cout<<mx<<endl;
            }
            else
            {
                cout<<"impossible"<<endl;
                break;
            }
        }
            
    }
    

    return 0;
}

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