제출 #579646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579646		jasmin	Event Hopping (BOI22_events)	C++17	0 / 100	212 ms	32744 KiB

events

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

void subtask1(int n, int q, vector<pair<int,int> >& e, vector<pair<int,int> >& query){
    vector<int> next(n, -1);
    set<int> active;
    vector<pair<int, pair<int,int> > > time;
    for(int i=0; i<n; i++){
        time.push_back({e[i].first, {0, i}});
        time.push_back({e[i].second, {1, i}});
    }
    sort(time.begin(), time.end());
    int last=-1; int end=-1;
    for(auto elem: time){
        if(active.find(elem.second.second)!=active.end()){
            active.erase(elem.second.second);
            if(!active.empty()){
                next[elem.second.second]=*active.begin();
            }
            else if(end==e[elem.second.second].second){
                next[elem.second.second]=last;
            }
            end=e[elem.second.second].second;
            last=elem.second.second;
        }
        else{
            active.insert(elem.second.second);
        }
    }

    int l=25;
    vector<vector<int> > up(n, vector<int> (l, -1));
    for(int i=0; i<n; i++){
        up[i][0]=next[i];
        //cout << up[i][0] << " ";
    }
    //cout << "\n";
    for(int i=1; i<l; i++){
        for(int j=0; j<n; j++){
            if(up[j][i-1]!=-1){
                up[j][i]=up[up[j][i-1]][i-1];
            }
            //cout << up[j][i] << "  ";
        }
        //cout << "\n";
    }

    //cout << "hallo\n" << flush;
    
    for(int i=0; i<q; i++){
        int s=query[i].first-1;
        int t=query[i].second-1;

        int ans=0;
        //cout << "test\n" << flush;
        for(int j=l-1; j>=0; j--){
            //cout << s << " " << up[s][j] << " " << t << "\n" << flush;
            if(up[s][j]!=-1 && e[up[s][j]].second<=e[t].second){
                ans+=(1<<j);
                s=up[s][j];
            }

            if(s==t){
                break;
            }
        }

        if(s==t){
            cout << ans << "\n";
        }
        else{
            cout << "impossible\n";
        }
    }
}

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

    int n, q;
    cin >> n >> q;
    vector<pair<int,int> > e(n);
    for(int i=0; i<n; i++){
        cin >> e[i].first >> e[i].second;
    }
    vector<pair<int,int> > query(n);
    for(int i=0; i<q; i++){
        cin >> query[i].first >> query[i].second;
    }

    subtask1(n, q, e, query);
}

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