Submission #1086473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086473		vjudge1	Event Hopping (BOI22_events)	C++17	30 / 100	214 ms	16748 KiB

events

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

int const N = 1e5+10;

struct interval {
    int s, e;
    interval() = default;
    interval(int a, int b) : s(a), e(b) {}
    bool operator< (const interval& o) const {
        if (s == o.s) return e > o.e;
        return s < o.s;
    }
} IT[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
    interval it; 
    int idx, meta, prior;
    node *l, *r;
    node() = default;
    node(int i) : it(IT[i]), idx(i), meta(i), prior(rng()), l(0), r(0) {}
};
using pnode = node*;

pnode rt = nullptr;
void update(pnode u) {
    if (!u) return;
    u->meta = u->idx;
    if (u->l && IT[u->l->meta].e > IT[u->meta].e) u->meta = u->l->meta;
    if (u->r && IT[u->r->meta].e > IT[u->meta].e) u->meta = u->r->meta;
}
void split(pnode rt, pnode& l, pnode& r, int v) {
    if (!rt) return (void)(l=r=nullptr);
    if (v < rt->it.s) split(rt->l, l, rt->l, v), r = rt;
    else split(rt->r, rt->r, r, v), l = rt;
    update(rt);
}
void split(pnode rt, pnode& l, pnode& r, interval it) {
    if (!rt) return (void)(l=r=nullptr);
    if (it < rt->it) split(rt->l, l, rt->l, it), r = rt;
    else split(rt->r, rt->r, r, it), l = rt;
    update(rt);
}
void join(pnode& rt, pnode l, pnode r) {
    if (!l || !r) rt = l?:r;
    else if (l->prior > r->prior) join(l->r, l->r, r), rt = l;
    else join(r->l, l, r->l), rt = r;
    update(rt);
}
void add(int idx) {
    if (rt == nullptr) rt = new node(idx);
    else {
        pnode nn = new node(idx);
        pnode lv, rv;
        split(rt, lv, rv, nn->it);
        join(rt, lv, nn); join(rt, rt, rv);
    }
}

int sparse[17][N];
void dfs(pnode r) {
    if (!r) return;
    dfs(r->l);
    cerr << "[" << r->it.s << ", " << r->it.e << "] ";
    dfs(r->r);
}


int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> IT[i].s >> IT[i].e;
        add(i);
    }
    //dfs(rt); cerr << '\n';
    for (int i = 1; i <= n; ++i) {
        pnode lv, rv; split(rt, lv, rv, IT[i].e);
        //dfs(lv);
        //cerr << lv->meta << ' ';
        sparse[0][i] = lv->meta;
        join(rt, lv, rv);
    }
    //cerr << '\n';
    for (int b = 1; b < 17; ++b) {
        for (int i = 1; i <= n; ++i) sparse[b][i] = sparse[b-1][sparse[b-1][i]];
    }
    for (int i = 0; i < q; ++i) {
        int a, b; cin >> a >> b;
        if (a == b) {
            cout << 0 << '\n';
            continue;
        }


        if (IT[a].e > IT[b].e) {
            cout << "impossible\n";
        }
        else {
            int st = 0;
            for (int bb = 16; ~bb; --bb) {
                int idx = sparse[bb][a];
                if (IT[idx].e < IT[b].e) {
                    st += 1<<bb;
                    a = idx;
                }
            }
            if (IT[a].e >= IT[b].s) {
                ++st;
                cout << st << '\n';
            }
            else {
                ++st; a = sparse[0][a];
                if (IT[a].e != IT[b].e) {
                    cout << "impossible\n";
                }
                else {
                    cout << (st+1) << '\n';
                }
            }
        }
    }

}

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