제출 #1175888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175888		DanielPr8	Event Hopping (BOI22_events)	C++20	100 / 100	264 ms	38648 KiB

events

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define all(v) v.begin(),v.end()
#define pb push_back
vll val;

struct seg{
    ll n;
    vpl bl;
    seg(ll n):n(n){
        bl = vpl(n*2, {1e9,1e9});// {who, val}
    }
    pll com(pll a, pll b){
        if(a.s<b.s)return a;
        return b;
    }
    void upd(ll i, pll x){
        i+=n;
        bl[i] = com(bl[i], x);
        for(i/=2; i>0;i/=2){
            bl[i] = com(bl[i*2], bl[i*2+1]);
        }
    }
    ll que(ll a, ll b){
        pll ans = {1e9,1e9};
        for(a+=n,b+=n;a<=b;a/=2,b/=2){
            if(a%2==1)ans = com(ans, bl[a++]);
            if(b%2==0)ans = com(ans, bl[b--]);
        }
        return ans.f;
    }
};


ll fd(ll a){
    return lower_bound(all(val),a)-val.begin();
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, q, s, e, f=20;
    cin >> n >> q;
    vpl ev(n);
    set<ll> d;
    for(pll& i:ev){cin >> i.s >> i.f;d.insert(i.f);d.insert(i.s);}
    for(ll i:d)val.pb(i);
    ll N = 1<<(32-__builtin_clz(val.size()));
    seg *S = new seg(N);
    vvl nxt(f, vll(n));
    for(ll i = 0; i < n; ++i){
        S->upd(fd(ev[i].f), {i, fd(ev[i].s)});
    }
    for(ll i = 0; i < n; ++i){
        nxt[0][i] = S->que(fd(ev[i].s), fd(ev[i].f));
    }
    for(ll h = 1; h < f; ++h){
        for(ll i = 0; i < n; ++i){
            nxt[h][i] = nxt[h-1][nxt[h-1][i]];
        }
    }
    while(q--){
        cin >> e >> s;s--;e--;
        if(ev[s].f<ev[e].f){cout << "impossible\n";continue;}
        ll ans = 1e9, cur=0;
        for(ll h = f-1; h >= 0; --h){
            if(ev[nxt[h][s]].s<=ev[e].f)ans = min(ans, cur+(1<<h)+1);
            else{
                cur+=(1<<h);
                s = nxt[h][s];
            }
        }
        if(ev[s].s<=ev[e].f)ans = min(ans, 1ll);
        if(s==e)ans=0;
        if(ans==1e9)cout << "impossible\n";
        else cout << ans << "\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