Submission #227893

#	Time	Username	Problem	Language	Result	Execution time	Memory
227893		emil_physmath	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	797 ms	262148 KiB

sortbooks

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int a[1000'000];
vector<int> t[4000'000];
int tans[4000'000];
bool ans[1000'000];
int w[1000'000];

inline int Max(const vector<int>& x) { return x.back(); }
void Build(int v, int vl, int vr)
{
    if (vl == vr)
    {
        ans[v] = 0;
        t[v].push_back(a[vr]);
        return;
    }
    int m = vl + (vr - vl) / 2;
    Build(v * 2, vl, m);
    Build(v * 2 + 1, m + 1, vr);
    t[v].reserve(vr - vl + 1);
    merge(t[v * 2].begin(), t[v * 2].end(),
          t[v * 2 + 1].begin(), t[v * 2 + 1].end(),
          back_inserter(t[v]));
    t[v].shrink_to_fit();
    tans[v] = max(tans[v * 2], tans[v * 2 + 1]);
    auto smaller = lower_bound(t[v * 2 + 1].begin(), t[v * 2 + 1].end(), Max(t[v * 2]));
    if (smaller != t[v * 2 + 1].begin())
        tans[v] = max(tans[v], Max(t[v * 2]) + *--smaller);
}
struct UPD
{
    int v, maxAtLeft, q;
};
vector<UPD> upd;
int Query(int v, int vl, int vr, int l, int r, int maxAtLeft, int w, int q)
{
    if (l > vr || vl > r)
        return 0;
    if (l <= vl && vr <= r)
    {
        ans[q] = min(ans[q], tans[v] <= w);
        upd.push_back(UPD());
        upd.back().v = v;
        upd.back().maxAtLeft = maxAtLeft;
        upd.back().q = q;
        return Max(t[v]);
    }
    int vm = vl + (vr - vl) / 2;
    maxAtLeft = max(Query(v * 2, vl, vm, l, r, maxAtLeft, w, q), maxAtLeft);
    Query(v * 2 + 1, vm + 1, vr, l, r, maxAtLeft, w, q);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    Build(1, 0, n - 1);
    for (int i = 0; i < m; ++i)
    {
        ans[i] = 1;
        int l, r;
        cin >> l >> r >> w[i];
        --l; --r;
        Query(1, 0, n - 1, l, r, 0, w[i], i);
    }
    for (UPD x: upd)
    {
        int v = x.v, maxAtLeft = x.maxAtLeft, q = x.q;
        auto small = lower_bound(t[v].begin(), t[v].end(), maxAtLeft);
        if (small != t[v].begin())
            ans[q] = min(ans[q], maxAtLeft + *--small <= w[q]);
    }
    for (int i = 0; i < m; ++i)
        cout << ans[i] << '\n';
}

Compilation message (stderr)

sortbooks.cpp: In function 'int Query(int, int, int, int, int, int, int, int)':
sortbooks.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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