Submission #1294541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294541		k12_khoi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	590 ms	327680 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=1e6+5;

struct queries
{
    int L,R,K,ID;
} Q[N];

bool cmp_R(queries a,queries b)
{
    return a.R<b.R;
}

int n,request,u,v,x,l;
int a[N];
bool ans[N];
pii t[4*N];
vector <int> lazy[4*N];

void build(int id,int l,int r)
{
    lazy[id].clear();
    if (l==r)
    {
        t[id].X=0;
        t[id].Y=a[l];
        return;
    }
    int m=(l+r)/2;
    build(id*2,l,m);
    build(id*2+1,m+1,r);

    t[id].X=0;
    t[id].Y=max(t[id*2].Y,t[id*2+1].Y);
}

void down(int id)
{
    if (!lazy[id].empty())
    {
        for (int x:lazy[id])
        {
            if (t[id*2].Y>x)
            {
                t[id*2].X=max(t[id*2].X,t[id*2].Y+x);
                lazy[id*2].push_back(x);
            }
            if (t[id*2+1].Y>x)
            {
                t[id*2+1].X=max(t[id*2+1].X,t[id*2+1].Y+x);
                lazy[id*2+1].push_back(x);
            }
        }

        lazy[id].clear();
    }
}

void update(int id,int l,int r)
{
    if (u>r or v<l) return;
    if (u<=l and v>=r)
    {
        if (t[id].Y>x)
        {
            t[id].X=max(t[id].X,t[id].Y+x);
            lazy[id].push_back(x);
        }
        return;
    }

    down(id);
    int m=(l+r)/2;

    update(id*2,l,m);
    update(id*2+1,m+1,r);

    t[id].X=max(t[id*2].X,t[id*2+1].X);
}

int get(int id,int l,int r)
{
    if (u>r or v<l) return 0;
    if (u<=l and v>=r) return t[id].X;

    down(id);
    int m=(l+r)/2;

    return max(get(id*2,l,m),get(id*2+1,m+1,r));
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> request;
    for (int i=1;i<=n;i++)
    cin >> a[i];

    for (int i=1;i<=request;i++)
    {
        cin >> Q[i].L >> Q[i].R >> Q[i].K;
        Q[i].ID=i;
    }
    sort(Q+1,Q+request+1,cmp_R);


    build(1,1,n);

    l=1;
    for (int i=1;i<=request;i++)
    {
        while (l<=Q[i].R)
        {
            u=1;
            v=l-1;
            x=a[l];
            update(1,1,n);

            l++;
        }

        u=Q[i].L;
        v=Q[i].R-1;

        if (get(1,1,n)>Q[i].K) ans[Q[i].ID]=0;
        else ans[Q[i].ID]=1;
    }

    for (int i=1;i<=request;i++)
    cout << ans[i] << '\n';
}

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