Submission #1086558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086558		vjudge1	Event Hopping (BOI22_events)	C++17	30 / 100	410 ms	22228 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) {}
} IT[N];
bool it_cmp(interval& a, interval& b) {
    if (a.s == b.s) return a.e > b.e;
    return a.s < b.s;
}

bool it_cmp2(interval& a, interval& b) {
    if (a.e == b.e) return a.s > b.s;
    return a.e < b.e;
}

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, rt2=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 update2(pnode u) {
    if (!u) return;
    u->meta = u->idx;
    if (u->l && IT[u->l->meta].s < IT[u->meta].s) u->meta = u->l->meta;
    if (u->r && IT[u->r->meta].s < IT[u->meta].s) u->meta = u->r->meta;
}

void split(pnode rt, pnode& l, pnode& r, int v, int const type = 0) {
    if (!rt) return (void)(l=r=nullptr);
    int flag = type?(v<rt->it.e):(v<rt->it.s);

    if (flag) split(rt->l, l, rt->l, v, type), r = rt;
    else split(rt->r, rt->r, r, v, type), l = rt;
    if (type) update2(rt);
    else update(rt);
}
void split(pnode rt, pnode& l, pnode& r, interval it, int const type = 0) {
    if (!rt) return (void)(l=r=nullptr);
    int flag = type?it_cmp2(it, rt->it):it_cmp(it, rt->it);

    if (flag) split(rt->l, l, rt->l, it, type), r = rt;
    else split(rt->r, rt->r, r, it, type), l = rt;
    if (type) update2(rt);
    else update(rt);
}
void join(pnode& rt, pnode l, pnode r, int const type = 0) {
    if (!l || !r) rt = l?:r;
    else if (l->prior > r->prior) join(l->r, l->r, r, type), rt = l;
    else join(r->l, l, r->l, type), rt = r;
    if (type) update2(rt);
    else update(rt);
}
void add(int idx) {
    if (rt == nullptr) {
        rt = new node(idx);
        rt2 = new node(idx);
    }
    else {
        pnode nn = new node(idx);
        pnode lv, rv;
        split(rt, lv, rv, nn->it, 0);
        join(rt, lv, nn, 0); join(rt, rt, rv, 0);

        pnode nn2 = new node(idx);
        split(rt2, lv, rv, nn2->it, 1);
        join(rt2, lv, nn2, 1); join(rt2, rt2, rv, 1);
    }
}

int sparse[18][N];
int border[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, mv, rv; split(rt, lv, rv, IT[i].e);
        //dfs(lv);
        //cerr << lv->meta << ' ';
        sparse[0][i] = lv->meta;
        join(rt, lv, rv);

        split(rt2, lv, rv, IT[i].e, 1);
        split(lv, lv, mv, IT[i].s-1, 1);
        border[i] = IT[mv->meta].s;
        join(rt2, lv, mv, 1);
        join(rt2, rt2, rv, 1);
    }
    //cerr << '\n';
    for (int b = 1; b < 18; ++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 if (IT[sparse[17][a]].e < IT[b].s) {
            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 {
                if (border[b] > IT[a].e) {
                    cout << "impossible\n";
                }
                else {
                    cout << (st+2) << '\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