Submission #1246478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246478		svtk	Event Hopping (BOI22_events)	C++20	10 / 100	1596 ms	1092 KiB

events

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
using namespace std;
using pii = pair<int, int>;
using pipii = pair<int, pii>;
using ppiii = pair<pii, int>;

const int N = 100'000;
const int Q = 100'000;

int n, q;
pii events[N];
int ans[Q];

int pos(int s, int e){
    return events[s].second >= events[e].first and events[s].second <= events[e].second;
}

int main(){
    cin >> n >> q;
    for(int i=0; i<n; i++){
        cin >> events[i].first >> events[i].second;
    }

    for(int qi=0; qi<q; qi++){
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        int count = 0;
        while(s!=e){
            int best = s;
            for(int i=0; i<n; i++){
                if(pos(s, i) and events[i].second <= events[e].second){
                    if(i==e or events[i].second > events[best].second){
                        best = i;
                    }
                }
            }
            if(best==s){
                count = -1;
                break;
            } else {
                count++;
                s = best;
            }
        }
        ans[qi] = count;
    }
    for(int i=0; i<q; i++){
        if(ans[i]==-1) cout << "impossible\n";
        else cout << ans[i] << '\n';
    }

    return 0;
}

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