oj.uz

Submission #1086558

# Submission time Handle Problem Language Result Execution time Memory
1086558 2024-09-11T03:28:22 Z vjudge1 Event Hopping (BOI22_events) C++17
30 / 100
 410 ms 22228 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 342 ms 21544 KB Output is correct
3 Correct 351 ms 21584 KB Output is correct
4 Correct 356 ms 21584 KB Output is correct
5 Correct 363 ms 21660 KB Output is correct
6 Correct 369 ms 21588 KB Output is correct
7 Correct 378 ms 21844 KB Output is correct
8 Correct 332 ms 22196 KB Output is correct
9 Correct 343 ms 22228 KB Output is correct
10 Correct 342 ms 22112 KB Output is correct
11 Correct 389 ms 22172 KB Output is correct
12 Correct 140 ms 21332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6720 KB Output is correct
4 Correct 2 ms 6720 KB Output is correct
5 Incorrect 2 ms 6624 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6720 KB Output is correct
4 Correct 2 ms 6720 KB Output is correct
5 Incorrect 2 ms 6624 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6720 KB Output is correct
4 Correct 2 ms 6720 KB Output is correct
5 Incorrect 2 ms 6624 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 21584 KB Output is correct
2 Correct 373 ms 21668 KB Output is correct
3 Correct 362 ms 21588 KB Output is correct
4 Correct 346 ms 21992 KB Output is correct
5 Correct 354 ms 22040 KB Output is correct
6 Correct 398 ms 21844 KB Output is correct
7 Correct 410 ms 21724 KB Output is correct
8 Correct 384 ms 21840 KB Output is correct
9 Correct 255 ms 19928 KB Output is correct
10 Correct 404 ms 21464 KB Output is correct
11 Correct 365 ms 21332 KB Output is correct
12 Correct 379 ms 21332 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 342 ms 21544 KB Output is correct
3 Correct 351 ms 21584 KB Output is correct
4 Correct 356 ms 21584 KB Output is correct
5 Correct 363 ms 21660 KB Output is correct
6 Correct 369 ms 21588 KB Output is correct
7 Correct 378 ms 21844 KB Output is correct
8 Correct 332 ms 22196 KB Output is correct
9 Correct 343 ms 22228 KB Output is correct
10 Correct 342 ms 22112 KB Output is correct
11 Correct 389 ms 22172 KB Output is correct
12 Correct 140 ms 21332 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6720 KB Output is correct
16 Correct 2 ms 6720 KB Output is correct
17 Incorrect 2 ms 6624 KB Output isn't correct
18 Halted 0 ms 0 KB -