Submission #227716

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

sortbooks

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

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

int Max(const vector<int>& x)
{
    if (x.empty())
        cerr << "Max got empty vector as argument.";
    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);
    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();
    ans[v] = max(ans[v * 2], ans[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())
    {
        --smaller;
        ans[v] = max(ans[v], Max(t[v * 2]) + *smaller);
    }
}
pair<bool, int> Query(int v, int vl, int vr, int l, int r, int w, int maxAtLeft/* = 0*/)
{
    // cerr << "(" << l << ", " << r << ") / (" << vl << ", " << vr << ")\n";
    if (vl == l && vr == r)
    {
        bool res = ans[v] <= w;
        if (!res)
            return {res, 0};
        auto small = lower_bound(t[v].begin(), t[v].end(), maxAtLeft);
        if (small != t[v].begin())
        {
            --small;
            res = min(res, (maxAtLeft + *small) <= w);
        }
        // cerr << "(l = " << l << ", r = " << r << ") / " << "(vl = " << vl << ", vr = " << vr << ") returns " << res << endl;
        return {res, Max(t[v])};
    }
    int m = vl + (vr - vl) / 2;
    if (r <= m)
        return Query(v * 2, vl, m, l, r, w, maxAtLeft);
    else if (l > m)
        return Query(v * 2 + 1, m + 1, vr, l, r, w, maxAtLeft);
    pair<bool, int> q1 = Query(v * 2, vl, m, l, m, w, maxAtLeft);
    bool res = q1.first;
    if (!res) return {false, 0};
    maxAtLeft = max(maxAtLeft, q1.second);
    pair<bool, int> q2 = Query(v * 2 + 1, m + 1, vr, m + 1, r, w, maxAtLeft);
    res = min(res, q2.first);
    // cerr << "(l = " << l << ", r = " << r << ") / " << "(vl = " << vl << ", vr = " << vr << ") returns " << res << endl;
    return {res, max(q1.second, q2.second)};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    const int maxW = 30;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    if (n > 200000 && false)
    {
        vector<int> sortedTill(n);
        for (int i = n - 1; i >= 0; --i)
        {
            sortedTill[i] = i;
            if (i + 1 < n && a[i] <= a[i + 1])
                sortedTill[i] = sortedTill[i + 1];
        }
        while (m--)
        {
            int l, r, w;
            cin >> l >> r >> w; --l; --r;
            cout << (sortedTill[l] >= r) << '\n';
        }
        return 0;
    }
    Build(1, 0, n - 1);
    while (m--)
    {
        int l, r, w;
        /*w = rand() % (maxW + 1);
        l = rand() % n;
        r = rand() % n;
        if (l > r) swap(l, r);*/
        cin >> l >> r >> w;
        --l; --r;
        cout << Query(1, 0, n - 1, l, r, w, 0).first << '\n';
        // cerr << l << ' ' << r << " w = " << w << endl;
        // cout << (int printed = ( <= w);) << '\n';
        /*int ans = 1;
        for (int i = l; i <= r; ++i)
            for (int j = i + 1; j <= r; ++j)
                if (a[i] > a[j] && a[i] + a[j] > w)
                    ans = 0;
        cerr << "printed: " << printed << endl;
        cerr << "answer: " << ans << endl;*/
        // cerr << ((ans == printed) ? "OK\n" : "WA\n");
    }
}
/*
10 1
2 4 6 4 3 5 6 3 2 4
5 8 10
*/

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:74:15: warning: unused variable 'maxW' [-Wunused-variable]
     const int maxW = 30;
               ^~~~

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