Submission #228294

#	Time	Username	Problem	Language	Result	Execution time	Memory
228294		emil_physmath	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1289 ms	76100 KiB

sortbooks

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

int a[1000'000], ans[1000'000], t[4000'000], t1[4000'000];

void Build(int v, int vl, int vr)
{
    if (vl == vr)
    {
        t[v] = a[vr];
        return;
    }
    int vm = (vl + vr) / 2;
    Build(v * 2, vl, vm);
    Build(v * 2 + 1, vm + 1, vr);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int Grt(int v, int vl, int vr, int i)
{
    if (i <= vl || t[v] <= a[i])
        return -1;
    if (vl == vr)
        return t[v] > a[i] ? vr : -1;
    int vm = (vl + vr) / 2;
    int res = Grt(v * 2 + 1, vm + 1, vr, i);
    if (res != -1)
        return res;
    return Grt(v * 2, vl, vm, i);
}
void Maxi(int v, int vl, int vr, int l, int r, int val)
{
    if (l > vr || vl > r)
        return;
    if (l <= vl && vr <= r)
    {
        t1[v] = max(t1[v], val);
        return;
    }
    int vm = (vl + vr) / 2;
    Maxi(v * 2, vl, vm, l, r, val);
    Maxi(v * 2 + 1, vm + 1, vr, l, r, val);
}
int GetMax(int v, int vl, int vr, int i)
{
    if (vl == vr)
        return t1[v];
    int vm = (vl + vr) / 2;
    if (i <= vm)
        return max(GetMax(v * 2, vl, vm, i), t1[v]);
    return max(GetMax(v * 2 + 1, vm + 1, vr, i), t1[v]);
}
int main()
{
    ios::sync_with_stdio(0);
    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);
    struct Query
    {
        int l, r, w, ind;
        bool ans;
    };
    vector<Query> q(m);
    for (int i = 0; i < m; ++i)
    {
        q[i].ind = i;
        cin >> q[i].l >> q[i].r >> q[i].w;
        --q[i].l; --q[i].r;
    }
    sort(q.begin(), q.end(), [](const Query& l, const Query& r) {
         return l.r < r.r;
    });
    int maxr = -1;
    for (int i = 0; i < m; ++i)
    {
        int l = q[i].l, r = q[i].r, w = q[i].w;
        while (maxr < r)
        {
            int j = Grt(1, 0, n - 1, ++maxr);
            if (j != -1)
                Maxi(1, 0, n - 1, 0, j, a[j] + a[maxr]);
        }
        q[i].ans = GetMax(1, 0, n - 1, l) <= w;
    }
    sort(q.begin(), q.end(), [](const Query& l, const Query& r) {
         return l.ind < r.ind;
    });
    for (int i = 0; i < m; ++i)
        cout << q[i].ans << '\n';
}

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