Submission #681550

#	Time	Username	Problem	Language	Result	Execution time	Memory
681550		finn__	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2864 ms	213036 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

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

    size_t n, m;
    cin >> n >> m;

    size_t l = 1 << (32 - __builtin_clz(n));
    vector<vector<unsigned>> tree(2 * l);
    vector<unsigned> max_inv(2 * l, 0);

    for (size_t i = 0; i < n; i++)
    {
        unsigned x;
        cin >> x;
        tree[l + i] = {x};
    }

    for (size_t i = n; i < l; i++)
        tree[l + i] = {UINT_MAX / 2};

    for (size_t i = l - 1; i; i--)
    {
        auto it = tree[2 * i].begin();
        auto jt = tree[2 * i + 1].begin();

        while (it != tree[2 * i].end() && jt != tree[2 * i + 1].end())
        {
            if (*it < *jt)
                tree[i].push_back(*it++);
            else
                tree[i].push_back(*jt++);
        }

        while (it != tree[2 * i].end())
            tree[i].push_back(*it++);
        while (jt != tree[2 * i + 1].end())
            tree[i].push_back(*jt++);

        max_inv[i] = max(max_inv[2 * i], max_inv[2 * i + 1]);
        jt = lower_bound(tree[2 * i + 1].begin(), tree[2 * i + 1].end(), tree[2 * i].back());
        if (jt != tree[2 * i + 1].begin())
            max_inv[i] = max(max_inv[i], tree[2 * i].back() + *(jt - 1));
    }

    for (size_t i = 0; i < m; i++)
    {
        size_t u, v;
        unsigned k, y = 0, z = 0;
        cin >> u >> v >> k;

        u += l - 1, v += l - 1;
        vector<size_t> comb1, comb2;

        while (u <= v)
        {
            if (u & 1)
                comb1.push_back(u++);

            if (!(v & 1))
                comb2.push_back(v--);

            u >>= 1;
            v >>= 1;
        }

        for (auto it = comb1.begin(); it != comb1.end(); it++)
        {
            z = max(z, max_inv[*it]);
            auto jt = lower_bound(tree[*it].begin(), tree[*it].end(), y);

            if (jt != tree[*it].begin())
                z = max(z, y + *(jt - 1));
            y = max(y, tree[*it].back());
        }

        for (auto it = comb2.rbegin(); it != comb2.rend(); it++)
        {
            z = max(z, max_inv[*it]);
            auto jt = lower_bound(tree[*it].begin(), tree[*it].end(), y);

            if (jt != tree[*it].begin())
                z = max(z, y + *(jt - 1));
            y = max(y, tree[*it].back());
        }

        cout << (int)(z <= k) << '\n';
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23