제출 #502648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502648		tim	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1345 ms	40488 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[5000010], ans[5000010], Max, y, l, r, k, n, m, a[5000010], b[5000010], A, B;

void build (int l, int r, int x)
{
    if (r < l) return;
    if (l == r)
    {
        mx[x] = w[l];
        ans[x] = 0;
        a[x] = 0;
        b[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]);
    if (ans[x * 2] > ans[x * 2 + 1])
    {
        ans[x] = ans[x * 2];
        a[x] = a[x * 2];
        b[x] = b[x * 2];
    }
    else
    {
        ans[x] = ans[x * 2 + 1];
        a[x] = a[x * 2 + 1];
        b[x] = b[x * 2 + 1];
    }
    if (mx[x * 2] > a[x * 2 + 1] and ans[x] < mx[x * 2] + a[x * 2 + 1] and a[x * 2 + 1] != 0)
    {
        ans[x] = mx[x * 2] + a[x * 2 + 1];
        a[x] = mx[x * 2];
        b[x] = a[x * 2 + 1];
    }
    if (mx[x * 2] > b[x * 2 + 1] and ans[x] < mx[x * 2] + b[x * 2 + 1] and b[x * 2 + 1] != 0)
    {
        ans[x] = mx[x * 2] + b[x * 2 + 1];
        a[x] = mx[x * 2];
        b[x] = b[x * 2 + 1];
    }
    if (mx[x * 2] > mx[x * 2 + 1] and ans[x] < mx[x * 2] + mx[x * 2 + 1])
    {
        ans[x] = mx[x * 2] + mx[x * 2 + 1];
        a[x] = mx[x * 2];
        b[x] = mx[x * 2 + 1];
    }
}

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];
            A = a[x];
            B = b[x];

        }
        else
        {
            if (ans[x] > y)
            {
                y = ans[x];
                A = a[x];
                B = b[x];
            }
            if (Max > a[x] and y < Max + a[x] and a[x] != 0)
            {
                y = Max + a[x];
                A = Max;
                B = a[x];
            }
            if (Max > b[x] and y < Max + b[x] and b[x] != 0)
            {
                y = Max + b[x];
                A = Max;
                B = b[x];
            }
            if (Max > mx[x] and y < Max + mx[x])
            {
                y = Max + mx[x];
                A = Max;
                B = mx[x];
            }
            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;
        A = 0;
        B = 0;
        get (1, n, l, r, 1);
        if (y <= k) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

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