Submission #1011225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011225		Forested	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1458 ms	69580 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25