Submission #1116979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116979		0x34c	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	289 ms	67764 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;

struct block
{
    int head, l, r;

    bool operator<(const block &y) const
    {
        return head < y.head;
    }
};

struct qry
{
    int t, i, idx;
};

struct segtree
{
private:
    vector<int> tree;
    int n;

    void update(int idx, int val, int v, int tl, int tr)
    {
        if (tl == tr)
            tree[v] = val;
        else
        {
            int m = (tl + tr) / 2;
            if (idx <= m)
                update(idx, val, 2 * v, tl, m);
            else
                update(idx, val, 2 * v + 1, m + 1, tr);
            tree[v] = tree[2 * v] + tree[2 * v + 1];
        }
    }

    pii query(int idx, int v, int tl, int tr)
    {
        if (tl == tr)
            return {tl, idx};
        else
        {
            int m = (tl + tr) / 2;
            if (tree[2 * v] > idx)
                return query(idx, 2 * v, tl, m);
            else
                return query(idx - tree[2 * v], 2 * v + 1, m + 1, tr);
        }
    }

public:
    segtree(int _n)
    {
        n = _n;
        tree.resize(4 * n, 0);
    }

    void update(int idx, int val)
    {
        return update(idx, val, 1, 0, n - 1);
    }

    pii query(int idx)
    {
        return query(idx, 1, 0, n - 1);
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;

    vector<int> arr(N);
    vector<int> nxt(N, -1), res(Q, 0);
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    vector<qry> queries(Q);
    for (int i = 0; i < Q; i++)
    {
        cin >> queries[i].t >> queries[i].i;
        queries[i].i--;
        queries[i].t = min(queries[i].t, N);
        queries[i].idx = i;
    }

    sort(queries.begin(), queries.end(), [](qry &a, qry &b)
         { return a.t < b.t; });

    int q_idx = 0;
    while (q_idx < Q && queries[q_idx].t == 0)
    {
        res[queries[q_idx].idx] = arr[queries[q_idx].i];
        q_idx++;
    }

    stack<int> stk;
    for (int i = N - 1; i >= 0; i--)
    {
        while (!stk.empty() && arr[stk.top()] < arr[i])
            stk.pop();

        nxt[i] = stk.empty() ? N : stk.top();
        stk.push(i);
    }

    segtree tree(N + 1);
    vector<block> block_props(N + 1);
    set<block> blocks;
    int block_cnt = 0;
    for (int i = 0; i < N; i++)
    {
        block_props[arr[i]] = {arr[i], i, nxt[i] - 1};
        blocks.insert({arr[i], i, nxt[i] - 1});
        tree.update(arr[i], nxt[i] - i);
        block_cnt++;
        i = nxt[i] - 1;
    }

    vector<block> fixed_blocks;
    int idx = N - 1;
    int t = 0;
    while (idx != N / 2 - 1)
    {
        block b = *blocks.rbegin();
        blocks.erase(b);

        int sz = b.r - b.l + 1;
        idx -= sz;
        if (idx + 1 >= N / 2)
        {
            fixed_blocks.push_back(b);
            continue;
        }

        // we want to make the block smaller
        int k = N / 2 - 1 - idx - 1;
        blocks.insert({b.head, b.l, b.l + k});
        block_props[b.head] = {b.head, b.l, b.l + k};
        tree.update(b.head, k + 1);
        idx += k + 1;

        for (int i = b.l + k + 1; i <= b.r; i = nxt[i])
        {
            int j = nxt[i];
            blocks.insert({arr[i], i, j - 1});
            block_props[arr[i]] = {arr[i], i, j - 1};
            tree.update(arr[i], j - i);
            idx += j - i;
        }
        t++;

        while (q_idx < Q && queries[q_idx].t == t)
        {
            int fidx = queries[q_idx].i;
            pii fres = tree.query(fidx);
            res[queries[q_idx].idx] = arr[block_props[fres.first].l + fres.second];
            q_idx++;
        }
    }

    while (q_idx < Q)
    {
        int fidx = queries[q_idx].i;
        pii fres = tree.query(fidx);
        res[queries[q_idx].idx] = arr[block_props[fres.first].l + fres.second];
        q_idx++;
    }

    // while (!blocks.empty())
    // {
    //     fixed_blocks.push_back(*blocks.rbegin());
    //     blocks.erase(*blocks.rbegin());
    // }

    // reverse(fixed_blocks.begin(), fixed_blocks.end());

    for (int q : res)
        cout << q << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25