Submission #1201589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201589		Unforgettablepl	Event Hopping (BOI22_events)	C++20	100 / 100	623 ms	86128 KiB

events

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

#define int long long

struct sparsefenwick{
    map<int,pair<int,int>> tree;
    int N;
    sparsefenwick(int N):N(N){}
    void update(int k,pair<int,int> x){
        while(k<=N){
            if(tree.count(k))tree[k]=min(tree[k],x);
            else tree[k]=x;
            k+=k&-k;
        }
    }
    pair<int,int> get(int k){
        pair<int,int> ans = {2e9,2e9};
        while(k){
            if(tree.count(k))ans=min(ans,tree[k]);
            k-=k&-k;
        }
        return ans;
    }
};


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin >> N >> Q;
    vector<int> s(N+1),e(N+1);
    for(int i=1;i<=N;i++)cin>>s[i]>>e[i];
    vector liftForward(N+1,vector<int>(17));
    {
        vector<tuple<int,bool,int>> events;
        for(int i=1;i<=N;i++){
            events.emplace_back(s[i],false,i);
            events.emplace_back(e[i],true,i);
        }
        sort(events.begin(),events.end());
        pair<int,int> maxi = {0,0};
        for(auto&[tim,type,idx]:events){
            maxi=max(maxi,{e[idx],idx});
            if(type){
                liftForward[idx][0]=maxi.second;
                if(liftForward[idx][0]==idx)liftForward[idx][0]=0;
            }
        }
    }
    vector liftBackward(N+1,vector<int>(17));
    {
        vector<tuple<int,bool,int>> events;
        for(int i=1;i<=N;i++){
            events.emplace_back(s[i],false,i);
            events.emplace_back(e[i],true,i);
        }
        sort(events.rbegin(),events.rend());
        sparsefenwick bit(1e9);
        for(auto&[tim,type,idx]:events){
            if(!type){
                liftBackward[idx][0]=bit.get(e[idx]).second;
                if(liftBackward[idx][0]==idx)liftBackward[idx][0]=0;
            } else {
                bit.update(e[idx],{s[idx],idx});
            }
        }
    }
    s[0]=-1;
    e[0]=2e9;
    {
        for(int bit=1;bit<17;bit++){
            for(int i=1;i<=N;i++){
                liftForward[i][bit] = liftForward[liftForward[i][bit-1]][bit-1];
                liftBackward[i][bit] = liftBackward[liftBackward[i][bit-1]][bit-1];
            }
        }
    }
    auto getHighestBefore = [&](int x,int limit){
        int jumps = 0;
        for(int bit=16;bit>=0;bit--){
            if(e[liftForward[x][bit]]>limit)continue;
            x = liftForward[x][bit];
            jumps += 1<<bit;
        }
        return make_pair(jumps,x);
    };
    auto getHighestBeforeRight = [&](int x,int limit){
        int jumps = 0;
        for(int bit=16;bit>=0;bit--){
            if(s[liftBackward[x][bit]]<=limit)continue;
            x = liftBackward[x][bit];
            jumps += 1<<bit;
        }
        if(s[x]>limit and liftBackward[x][0]!=0){
            jumps++;
            x = liftBackward[x][0];
        }
        return make_pair(jumps,x);
    };
    for(int i=1;i<=Q;i++){
        int a,b;cin>>a>>b;
        auto [leftMoves,leftHand] = getHighestBefore(a,s[b]-1);
        auto [rightMoves,rightHand] = getHighestBeforeRight(b,e[leftHand]);
        int ans = leftMoves+rightMoves;
        if(leftHand!=rightHand)ans++;
        if(s[rightHand]<=e[leftHand] and e[leftHand]<=e[rightHand])cout << ans << '\n';
        else cout << "impossible\n";
    }
}

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