Submission #951680

#	Time	Username	Problem	Language	Result	Execution time	Memory
951680		phoenix0423	Event Hopping (BOI22_events)	C++17	100 / 100	159 ms	37864 KiB

events

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
const int INF = 1e18;
int succ[maxn][18];

struct info{
    int l, r, id;
    info(){}
    info(int _l, int _r, int _id) : l(_l), r(_r), id(_id){}
    bool operator < (const info& other) const{
        return r < other.r;
    }
};
vector<int> val;
int getid(int x){ return lower_bound(val.begin(), val.end(), x) - val.begin();}

pll st[maxn * 4];
pll op(pll a, pll b){
    if(a.f < b.f) return a;
    return b;
}
void upd(int pos, int val, int id, int v = 1, int l = 0, int r = maxn - 1){
    if(l == r){
        if(st[v].f > val) st[v] = {val, id};
        return;
    }
    int m = (l + r) / 2;
    if(pos <= m) upd(pos, val, id, v * 2, l, m);
    else upd(pos, val, id, v * 2 + 1, m + 1, r);
    st[v] = op(st[v * 2], st[v * 2 + 1]);
}

pll qry(int l, int r, int v = 1, int L = 0, int R = maxn - 1){
    if(l > R || r < L) return {INF, -1};
    if(l <= L && r >= R) return st[v];
    int m = (L + R) / 2;
    return op(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}

signed main(void){
    fastio;
    int n, q;
    cin>>n>>q;
    for(int i = 0; i < maxn * 4; i++) st[i] = {INF, -1};
    vector<info> e(n), c(n);
    for(int i = 0; i < n; i++){
        int l, r;
        cin>>l>>r;
        val.pb(l), val.pb(r);
        e[i] = info(l, r, i);
    }
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    for(int i = 0; i < n; i++) e[i].l = getid(e[i].l), e[i].r = getid(e[i].r);
    c = e;
    sort(e.begin(), e.end());
    for(int i = 0; i < n; i++){
        int t = e[i].r;
        int tmp = i;
        while(tmp < n && e[tmp].r == t){
            upd(e[tmp].r, e[tmp].l, e[tmp].id);
            tmp++;
        }
        while(i < n && e[i].r == t){
            succ[e[i].id][0] = qry(e[i].l, e[i].r).s;
            if(succ[e[i].id][0] == -1) succ[e[i].id][0] = e[i].id;
            i++;
        }
        i--;
    }
    for(int j = 1; j < 18; j++){
        for(int i = 0; i < n; i++) succ[i][j] = succ[succ[i][j - 1]][j - 1];
    }
    while(q--){
        int s, t;
        cin>>s>>t;
        s--, t--;
        if(s == t){
            cout<<0<<"\n";
            continue;
        }
        if(c[s].r >= c[t].l && c[s].r <= c[t].r){
            cout<<1<<"\n";
            continue;
        }
        int ans = 0;
        for(int i = 17; i >= 0; i--){
            if(c[succ[t][i]].l > c[s].r) t = succ[t][i], ans += (1 << i);
        }
        if(c[succ[t][0]].l <= c[s].r && c[succ[t][0]].r >= c[s].r) cout<<ans + 2<<"\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