Submission #1188175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188175		Uasoni	Event Hopping (BOI22_events)	C++20	100 / 100	455 ms	135384 KiB

events

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

const int MAXN = 1e5+5, LMAXN = 20, MAXP = 1e9+5, INF = 2e9;
int n, q, l[MAXN], r[MAXN];

struct N {
    pii v = {INF, 0}; int l, r;
} stree[80*MAXN]; int ptr = 1;
void create(int i) {
    if(!stree[i].l) stree[i].l = ++ptr;
    if(!stree[i].r) stree[i].r = ++ptr;
}
void update(int p, pii v, int i = 1, int l = 1, int r = MAXP) {
    if(l == r) return void(stree[i].v = min(stree[i].v, v));
    create(i);
    int mid = (l+r)/2;
    if(p <= mid) update(p, v, stree[i].l, l, mid);
    else update(p, v, stree[i].r, mid+1, r);
    stree[i].v = min(stree[stree[i].l].v, stree[stree[i].r].v);
}
pii query(int lq, int rq, int i = 1, int l = 1, int r = MAXP) {
    if(!i) return {INF, 0};
    if(lq <= l && r <= rq) return stree[i].v;
    int mid = (l+r)/2; pii ret = {INF, 0};
    if(lq <= mid) ret = min(ret, query(lq, rq, stree[i].l, l, mid));
    if(rq > mid) ret = min(ret, query(lq, rq, stree[i].r, mid+1, r));
    return ret;
}

int get_nxt(int i) {
    pii ret = query(l[i], r[i]);
    if(ret.first >= l[i]) return 0;
    else return ret.second;
}

int jmp[MAXN][LMAXN];
void precomp_jmp() {
    for(int i = 1; i <= n; i++) jmp[i][0] = get_nxt(i);
    for(int j = 1; j < LMAXN; j++)
        for(int i = 1; i <= n; i++)
            jmp[i][j] = jmp[jmp[i][j-1]][j-1];
}

int make_jmp(int s, int e) {
    if(s == e) return 0;
    if(r[s] > r[e]) return -1;
    if(l[e] <= r[s]) return 1;
    int ans = 0;
    for(int j = LMAXN-1; j >= 0; j--) {
        if(jmp[e][j] && l[jmp[e][j]] > r[s]) {
            e = jmp[e][j];
            ans += (1 << j);
        }
    }
    if(!e) return -1;
    if(!jmp[e][0]) return -1;
    else return ans+2;
}

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        update(r[i], {l[i], i});
    }
    precomp_jmp();
    while(q--) {
        int s, e; cin >> s >> e;
        int ans = make_jmp(s, e);
        if(ans == -1) 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