Submission #1077266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077266		LIF	Event Hopping (BOI22_events)	C++14	25 / 100	1590 ms	9040 KiB

events

#include<bits/stdc++.h>
using namespace std;
int n,q,l[500005],r[500005];
int su[800005];
int dis[5005][5005];
int go[500005];
struct nod
{
    int ll;
    int rr;
    int id;
}node[500005];
bool cmp(nod x,nod y)
{
   if(x.rr == y.rr)return x.ll < y.ll;
   else return x.rr < y.rr;
}
int read()
{
    int x=0,f=1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x<<3) + (x<<1) + (ch-'0');
        ch = getchar();
    }
    return x*f;

}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        l[i] = read();r[i] = read();
        nod temp = nod{l[i],r[i],i};
        node[i] = temp;
    }
    sort(node+1,node+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int maxn = 1e9+100;
        go[i] = -1;
        for(int j=i-1;j>=1;j--)
        {
            if(node[j].rr >= node[i].ll && node[j].rr <= node[i].rr)
            {
                if(node[j].ll < maxn)
                {
                    maxn = node[j].ll;
                    go[i] = j;
                }
            }
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<node[i].ll<<" "<<node[i].rr<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<go[i]<<" ";
    // }
    // cout<<endl;
    while(q--)
    {
        int s,e;
        cin>>s>>e;
        if(e == s)
        {
            cout<<"0"<<endl;
            continue;
        }
        if(l[e] <= r[s] && r[s] <= r[e])
        {
            cout<<"1"<<endl;
            continue;
        }
        int cnt = 0;
        int now = -1;
        for(int i=1;i<=n;i++)
        {
            if(node[i].id == e)
            {
                now = i;
                break;
            }
        }
        bool can = false;
        while(now != -1)
        {
            int ll = node[now].ll;
            int rr = node[now].rr;
            if(ll <= r[s] && r[s] <= rr)
            {
                cnt++;
                can = true;
                break;
            }
            now = go[now];
            cnt++;
        }
        if(can == true)cout<<cnt<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}

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