Submission #502682

#	Time	Username	Problem	Language	Result	Execution time	Memory
502682		tim	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	3055 ms	247456 KiB

sortbooks

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define y1 tim
#define endl "\n"

#define sz(x) (long long)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int w[1000010], mx[4000010], ans[4000010], Max, y, l, r, k, n, m;
vector <int> v[4000010];

void build (int l, int r, int x)
{
    if (r < l) return;
    if (l == r)
    {
        mx[x] = w[l];
        v[x].push_back(w[l]);
        ans[x] = 0;

        return;
    }
    build (l, (l + r) / 2, x * 2);
    build ((l + r) / 2 + 1, r, x * 2 + 1);
    mx[x] = max (mx[x * 2], mx[x * 2 + 1]);
    v[x] = v[x * 2];
    ans[x] = max (ans[x * 2], ans[x * 2 + 1]);
    int mx1 = -1;
    for (auto i = v[x * 2 + 1].begin(); i != v[x * 2 + 1].end(); i++)
    {

        if (*i < mx[x * 2]) mx1 = *i;
        v[x].push_back(*i);
    }
    sort (v[x].begin(), v[x].end());
    if (mx1 != -1) ans[x] = max (ans[x], mx[x * 2] + mx1);
}

void get (int l, int r, int tl, int tr, int x)
{
    if (r < l) return;
    if (tl > r) return;
    if (tr < l) return;
    tl = max (l, tl);
    tr = min (r, tr);
    if (l == tl and r == tr)
    {
        if (Max == 0 and y == 0)
        {
            y = ans[x];
            Max = mx[x];
        }
        else
        {
            y = max (y, ans[x]);
            auto it = lower_bound(v[x].begin(), v[x].end(), Max);
            if (it != v[x].begin())
            {
                it--;
                y = max (y, Max + *it);
            }
            Max = max (Max, mx[x]);
        }
        return;
    }
    get (l, (l + r) / 2, tl, tr, x * 2);
    get ((l + r) / 2 + 1, r, tl, tr, x * 2 + 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    build (1, n, 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> l >> r >> k;
        y = 0;
        Max = 0;
        get (1, n, l, r, 1);
        if (y <= k) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

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