oj.uz

Submission #1011225

# Submission time Handle Problem Language Result Execution time Memory
1011225 2024-06-30T06:56:29 Z Forested Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1458 ms 69580 KB 
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

V<i32> riffle(V<i32> a) {
    V<i32> b;
    b.reserve(LEN(a));
    i32 l = 0, r = LEN(a) / 2;
    i32 lto = r, rto = LEN(a);
    while (LEN(b) < LEN(a)) {
        if (r == rto || (l < lto && a[l] < a[r])) {
            b.push_back(a[l++]);
        } else {
            b.push_back(a[r++]);
        }
    }
    return b;
}

mt19937 mt(998244353);

struct Node {
    i32 sz;
    Node *lch, *rch;
    i32 val, mx;
    Node() : sz(1), lch(nullptr), rch(nullptr), val(-1), mx(-1) {}
    void update() {
        sz = 1;
        mx = val;
        if (lch) {
            sz += lch->sz;
            chmax(mx, lch->mx);
        }
        if (rch) {
            sz += rch->sz;
            chmax(mx, rch->mx);
        }
    }
};

Node *merge(Node *l, Node *r) {
    if (!l) {
        return r;
    }
    if (!r) {
        return l;
    }
    if (mt() % (l->sz + r->sz) < l->sz) {
        l->rch = merge(l->rch, r);
        l->update();
        return l;
    } else {
        r->lch = merge(l, r->lch);
        r->update();
        return r;
    }
}

pair<Node *, Node *> split(Node *node, i32 x) {
    if (x == 0) {
        return pair<Node *, Node *>(nullptr, node);
    }
    if (x == node->sz) {
        return pair<Node *, Node *>(node, nullptr);
    }
    i32 lsz = (node->lch ? node->lch->sz : 0);
    if (x <= lsz) {
        auto [ll, lr] = split(node->lch, x);
        node->lch = lr;
        node->update();
        return pair<Node *, Node *>(ll, node);
    } else {
        x -= lsz + 1;
        auto [rl, rr] = split(node->rch, x);
        node->rch = rl;
        node->update();
        return pair<Node *, Node *>(node, rr);
    }
}

i32 get_front(Node *node) {
    if (node->lch) {
        return get_front(node->lch);
    } else {
        return node->val;
    }
}

i32 access(Node *node, i32 x) {
    i32 lsz = (node->lch ? node->lch->sz : 0);
    if (x < lsz) {
        return access(node->lch, x);
    }
    x -= lsz;
    if (x == 0) {
        return node->val;
    }
    x -= 1;
    return access(node->rch, x);
}

pair<Node *, Node *> split_max_t(Node *node, i32 t) {
    if (node->mx <= t) {
        return pair<Node *, Node *>(node, nullptr);
    }
    i32 lmx = (node->lch ? node->lch->mx : -1);
    if (lmx > t) {
        auto [ll, lr] = split_max_t(node->lch, t);
        node->lch = lr;
        node->update();
        return pair<Node *, Node *>(ll, node);
    } else if (node->val > t) {
        Node *tmp = node->lch;
        node->lch = nullptr;
        node->update();
        return pair<Node *, Node *>(tmp, node);
    } else {
        auto [rl, rr] = split_max_t(node->rch, t);
        node->rch = rl;
        node->update();
        return pair<Node *, Node *>(node, rr);
    }
}

pair<Node *, Node *> split_pref_max(Node *node) {
    i32 f = get_front(node);
    return split_max_t(node, f);
}

Node *build(const V<i32> &a, i32 l, i32 r) {
    Node *ret = new Node;
    i32 mid = (l + r) / 2;
    ret->val = a[mid];
    if (l < mid) {
        ret->lch = build(a, l, mid);
    }
    if (mid + 1 < r) {
        ret->rch = build(a, mid + 1, r);
    }
    ret->update();
    return ret;
}

void show(Node *node, i32 indent = 0) {
    if (node->lch) {
        show(node->lch, indent + 1);
    }
    cout << string(2 * indent, ' ') << node->val << ' ' << node->mx << '\n';
    if (node->rch) {
        show(node->rch, indent + 1);
    }
}

pair<bool, Node *> operate(Node *node) {
    i32 n = node->sz;
    auto [lh, rh] = split(node, n / 2);
    bool oper = false;
    while (rh) {
        auto [rl, rr] = split_pref_max(rh);
        if (lh->mx < rl->mx) {
            rh = merge(rl, rr);
            break;
        }
        auto [ll, lr] = split_max_t(lh, rl->mx);
        lh = merge(merge(ll, rl), lr);
        rh = rr;
        oper = true;
    }
    return pair<bool, Node *>(oper, merge(lh, rh));
}

void recollect(Node *node, V<i32> &buf) {
    if (node->lch) {
        recollect(node->lch, buf);
    }
    buf.push_back(node->val);
    if (node->rch) {
        recollect(node->rch, buf);
    }
}

int main() {
    i32 n, q;
    cin >> n >> q;
    V<i32> a(n);
    REP(i, n) {
        cin >> a[i];
    }
    V<i32> t(q), idx(q);
    REP(i, q) {
        cin >> t[i] >> idx[i];
        --idx[i];
    }
    map<i32, V<i32>> mt;
    REP(i, q) {
        mt[t[i]].push_back(i);
    }
    V<i32> ans(q, -1);
    Node *tree = build(a, 0, n);
    //show(tree);
    i32 x = 0;
    while (true) {
        if (mt.count(x)) for (i32 i : mt[x]) {
            ans[i] = access(tree, idx[i]);
        }
        auto [res, t2] = operate(tree);
        tree = t2;
        if (res) {
            ++x;
        } else {
            break;
        }
    }
    a.clear();
    recollect(tree, a);
    REP(i, q) {
        if (ans[i] == -1) {
            ans[i] = a[idx[i]];
        }
    }
    REP(i, q) {
        cout << ans[i] << '\n';
    }
}

Compilation message

Main.cpp: In function 'Node* merge(Node*, Node*)':
Main.cpp:78:32: warning: comparison of integer expressions of different signedness: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} and 'i32' {aka 'int'} [-Wsign-compare]
   78 |     if (mt() % (l->sz + r->sz) < l->sz) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 26488 KB Output is correct
2 Correct 384 ms 27104 KB Output is correct
3 Correct 354 ms 26452 KB Output is correct
4 Correct 339 ms 25608 KB Output is correct
5 Correct 365 ms 27984 KB Output is correct
6 Correct 347 ms 27728 KB Output is correct
7 Correct 393 ms 29096 KB Output is correct
8 Correct 335 ms 26448 KB Output is correct
9 Correct 336 ms 26708 KB Output is correct
10 Correct 311 ms 25936 KB Output is correct
11 Correct 330 ms 25936 KB Output is correct
12 Correct 301 ms 24788 KB Output is correct
13 Correct 327 ms 25772 KB Output is correct
14 Correct 359 ms 27044 KB Output is correct
15 Correct 331 ms 26596 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 304 ms 24928 KB Output is correct
18 Correct 317 ms 24744 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 40336 KB Output is correct
2 Correct 516 ms 46008 KB Output is correct
3 Correct 516 ms 38328 KB Output is correct
4 Correct 403 ms 38584 KB Output is correct
5 Correct 455 ms 39040 KB Output is correct
6 Correct 452 ms 38528 KB Output is correct
7 Correct 468 ms 45708 KB Output is correct
8 Correct 482 ms 43960 KB Output is correct
9 Correct 437 ms 38844 KB Output is correct
10 Correct 424 ms 42940 KB Output is correct
11 Correct 404 ms 37148 KB Output is correct
12 Correct 341 ms 36868 KB Output is correct
13 Correct 404 ms 42500 KB Output is correct
14 Correct 356 ms 38680 KB Output is correct
15 Correct 435 ms 44012 KB Output is correct
16 Correct 49 ms 11696 KB Output is correct
17 Correct 385 ms 40412 KB Output is correct
18 Correct 284 ms 35004 KB Output is correct
19 Correct 109 ms 17424 KB Output is correct
20 Correct 131 ms 18628 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 15572 KB Output is correct
2 Correct 126 ms 11996 KB Output is correct
3 Correct 166 ms 13332 KB Output is correct
4 Correct 99 ms 10452 KB Output is correct
5 Correct 160 ms 13348 KB Output is correct
6 Correct 98 ms 10576 KB Output is correct
7 Correct 153 ms 12324 KB Output is correct
8 Correct 115 ms 10832 KB Output is correct
9 Correct 155 ms 12056 KB Output is correct
10 Correct 75 ms 9172 KB Output is correct
11 Correct 82 ms 9496 KB Output is correct
12 Correct 76 ms 9092 KB Output is correct
13 Correct 80 ms 9296 KB Output is correct
14 Correct 79 ms 9392 KB Output is correct
15 Correct 71 ms 9136 KB Output is correct
16 Correct 21 ms 5976 KB Output is correct
17 Correct 62 ms 8652 KB Output is correct
18 Correct 62 ms 8656 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 26488 KB Output is correct
2 Correct 384 ms 27104 KB Output is correct
3 Correct 354 ms 26452 KB Output is correct
4 Correct 339 ms 25608 KB Output is correct
5 Correct 365 ms 27984 KB Output is correct
6 Correct 347 ms 27728 KB Output is correct
7 Correct 393 ms 29096 KB Output is correct
8 Correct 335 ms 26448 KB Output is correct
9 Correct 336 ms 26708 KB Output is correct
10 Correct 311 ms 25936 KB Output is correct
11 Correct 330 ms 25936 KB Output is correct
12 Correct 301 ms 24788 KB Output is correct
13 Correct 327 ms 25772 KB Output is correct
14 Correct 359 ms 27044 KB Output is correct
15 Correct 331 ms 26596 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 304 ms 24928 KB Output is correct
18 Correct 317 ms 24744 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 774 ms 40336 KB Output is correct
22 Correct 516 ms 46008 KB Output is correct
23 Correct 516 ms 38328 KB Output is correct
24 Correct 403 ms 38584 KB Output is correct
25 Correct 455 ms 39040 KB Output is correct
26 Correct 452 ms 38528 KB Output is correct
27 Correct 468 ms 45708 KB Output is correct
28 Correct 482 ms 43960 KB Output is correct
29 Correct 437 ms 38844 KB Output is correct
30 Correct 424 ms 42940 KB Output is correct
31 Correct 404 ms 37148 KB Output is correct
32 Correct 341 ms 36868 KB Output is correct
33 Correct 404 ms 42500 KB Output is correct
34 Correct 356 ms 38680 KB Output is correct
35 Correct 435 ms 44012 KB Output is correct
36 Correct 49 ms 11696 KB Output is correct
37 Correct 385 ms 40412 KB Output is correct
38 Correct 284 ms 35004 KB Output is correct
39 Correct 109 ms 17424 KB Output is correct
40 Correct 131 ms 18628 KB Output is correct
41 Correct 240 ms 15572 KB Output is correct
42 Correct 126 ms 11996 KB Output is correct
43 Correct 166 ms 13332 KB Output is correct
44 Correct 99 ms 10452 KB Output is correct
45 Correct 160 ms 13348 KB Output is correct
46 Correct 98 ms 10576 KB Output is correct
47 Correct 153 ms 12324 KB Output is correct
48 Correct 115 ms 10832 KB Output is correct
49 Correct 155 ms 12056 KB Output is correct
50 Correct 75 ms 9172 KB Output is correct
51 Correct 82 ms 9496 KB Output is correct
52 Correct 76 ms 9092 KB Output is correct
53 Correct 80 ms 9296 KB Output is correct
54 Correct 79 ms 9392 KB Output is correct
55 Correct 71 ms 9136 KB Output is correct
56 Correct 21 ms 5976 KB Output is correct
57 Correct 62 ms 8652 KB Output is correct
58 Correct 62 ms 8656 KB Output is correct
59 Correct 0 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1458 ms 69580 KB Output is correct
62 Correct 904 ms 54324 KB Output is correct
63 Correct 1121 ms 57476 KB Output is correct
64 Correct 925 ms 52304 KB Output is correct
65 Correct 979 ms 54864 KB Output is correct
66 Correct 841 ms 52308 KB Output is correct
67 Correct 777 ms 49460 KB Output is correct
68 Correct 755 ms 47604 KB Output is correct
69 Correct 885 ms 49708 KB Output is correct
70 Correct 675 ms 45852 KB Output is correct
71 Correct 585 ms 45908 KB Output is correct
72 Correct 730 ms 45648 KB Output is correct
73 Correct 633 ms 45424 KB Output is correct
74 Correct 741 ms 47816 KB Output is correct
75 Correct 686 ms 46476 KB Output is correct
76 Correct 41 ms 11696 KB Output is correct
77 Correct 504 ms 41724 KB Output is correct
78 Correct 506 ms 41648 KB Output is correct
79 Correct 0 ms 344 KB Output is correct
80 Correct 0 ms 348 KB Output is correct