oj.uz

Submission #681547

# Submission time Handle Problem Language Result Execution time Memory
681547 2023-01-13T09:47:05 Z finn__ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2809 ms 187536 KB 
#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 = 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++);
    }

    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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2809 ms 187536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 22272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -