Submission #1192258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192258		rainmar	Event Hopping (BOI22_events)	C++20	0 / 100	1595 ms	2212 KiB

events

#pragma optimize("Ofast")

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

bool funct(pair<int,int> a, pair<int,int> b) {
    if(a.first < b.first) return false;
    if(b.first < a.first) return true;
    if(a.second > b.second) return false;
    if(b.second >= a.second) return true;
    return false;
}

int main() {
    int N,Q; cin >> N >> Q;
    vector<pair<int,int>> events;
    for(int i = 0; i < N; i++) {
        int a,b; cin >> a >> b;
        events.push_back({b,a});
    }

    vector<pair<int,int>> stationary = events;

    sort(events.begin(),events.end(),funct);
    //cout << "\n--------\n";
    for(auto e : events) {
        //cout << e.first << " " << e.second << endl;
    }

    

    for(int i = 0; i < Q; i++) {
        //cout << "\n--------\n";
        //get the starting thing duh
        int k1,k2; cin >> k2 >> k1;
        k1--; k2--;
        if(k1 == k2) {cout << "0\n"; continue;}
        int start = stationary[k1].first, len = stationary[k1].second;
        int steps = 0;
        //cout << "start " << start << " len " << len << endl;
        int maxx = len;
        for(int x = 0; x < N; x++) {
            
            int suggestS = events[x].first;

            //cout << "start2 " << events[x].first << " len2 " << events[x].second << endl;

            if(events[x] == stationary[k2] and events[x].first < len) {steps++; break;}

            //ok ig?
            if(suggestS > start) {continue;}

            if(suggestS <= start and suggestS >= len) { //canditate
                //cout << "candidate " << maxx << " " << suggestS << " " << events[x].second << endl;
                maxx = min(maxx, events[x].second); 
                ////cout << maxx << endl;
            }

            if(len > suggestS) {
                //cout << maxx << " " << suggestS << endl;
                if(maxx <= suggestS){
                steps++;
                len = events[x].second;
                //cout << "moved forward " << maxx << endl;
                } else {
                    ////cout << "impossible\n";
                    steps = -1;
                    break;
                }
            } 
            
        }

        if(steps != -1 and steps != 0) cout << steps+1 << "\n"; else cout << "impossible\n";


    }


}

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