Submission #579638

#	Time	Username	Problem	Language	Result	Execution time	Memory
579638		wdjpng	Event Hopping (BOI22_events)	C++17	25 / 100	1594 ms	21612 KiB

events

#include <bits/stdc++.h>


#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >=0; i--)

using namespace std;

struct ev {int s,e;};
bool path(ev a, ev b)
{
    return b.s<=a.e&&b.e>=a.e;
}

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

    int n,q;
    cin>>n>>q;
    vector<ev>evs(n);
    for(auto& e: evs) cin>>e.s>>e.e;

    vector<vector<int>>up(n, vector<int>(20));
    rep(i,n)
    {
        int minn=1e12, mini = i;
        rep(j,n)
        {
            if(path(evs[j], evs[i])&&evs[j].s<minn) {
                minn=evs[j].s;
                mini=j;
            } 
        }
        up[i][0]=mini;
    }
    for(int j = 1; j <=20; j++) rep(i,n) up[i][j]=up[up[i][j-1]][j-1];

    rep(cq,q)
    {
        int s,e;
        cin>>s>>e;
        s--; e--;

        int sum = 0;
        int v = e;
        for(int j = 20; j>=0;j--) if(evs[up[v][j]].s>evs[s].e) {v=up[v][j]; sum+=1<<j;}
        if(evs[v].s>evs[s].e) {sum++; v=up[v][0];}
        if(!path(evs[s], evs[v])) cout<<"impossible\n";
        else {
            if(s!=v) sum++;
            cout<<sum<<'\n';
        }
    }
}

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