Submission #172967

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

sortbooks

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

int a[1000000];
set<int> t[4000000];
int ans[4000000];

int Max(const set<int>& x)
{
    if (x.empty())
        cerr << "Max got empty set as argument.";
    return *x.rbegin();
}
void Build(int v, int vl, int vr)
{
    if (vl == vr)
    {
        ans[v] = 0;
        t[v].insert(a[vr]);
        return;
    }
    int m = vl + (vr - vl) / 2;
    Build(v * 2, vl, m);
    Build(v * 2 + 1, m + 1, vr);
    t[v].insert(t[v * 2].begin(), t[v * 2].end());
    t[v].insert(t[v * 2 + 1].begin(), t[v * 2 + 1].end());
    ans[v] = max(ans[v * 2], ans[v * 2 + 1]);
    auto smaller = t[v * 2 + 1].lower_bound(Max(t[v * 2]));
    if (smaller != t[v * 2 + 1].begin())
    {
        --smaller;
        ans[v] = max(ans[v], Max(t[v * 2]) + *smaller);
    }
}
int Query(int v, int vl, int vr, int l, int r, int maxAtLeft = 0)
{
    // cerr << "(" << l << ", " << r << ") / (" << vl << ", " << vr << ")\n";
    if (vl == l && vr == r)
        return ans[v];
    int res = 0;
    auto small = t[v].lower_bound(Max(t[v * 2]));
    if (small != t[v].begin())
    {
        --small;
        res = max(res, maxAtLeft + *small);
    }
    int m = vl + (vr - vl) / 2;
    if (r <= m)
        return max(res, Query(v * 2, vl, m, l, r));
    else if (l > m)
        return max(res, Query(v * 2 + 1, m + 1, vr, l, r));

    res = max(res, Query(v * 2 + 1, m + 1, vr, m + 1, r, Max(t[v * 2])));
    res = max(res, Query(v * 2, vl, m, l, m));
    return res;
}
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);
    while (m--)
    {
        int l, r, w;
        cin >> l >> r >> w;
        cout << (Query(1, 0, n - 1, l - 1, r - 1) <= w) << '\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