Submission #681544

#	Time	Username	Problem	Language	Result	Execution time	Memory
681544		finn__	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2758 ms	181204 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);

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

    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++);
    }

    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++)
        {
            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++)
        {
            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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23