Submission #1294572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294572		k12_khoi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3096 ms	115964 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;
const int K=22;
const int oo=2e9+1;

int n,h,request,u,v,l,r,k;
int a[N],lg2[N],p[N][K],t[4*N],ma_ans[4*N];
bool ok;
stack <int> st;

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

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

void update(int t[],int id,int l,int r)
{
    if (l==r)
    {
        t[id]=v;
        return;
    }
    int m=(l+r)/2;
    if (u<=m) update(t,id*2,l,m);
    else update(t,id*2+1,m+1,r);

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

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

    int m=(l+r)/2;

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

void BuildSparseTable()
{
    lg2[1]=0;
    for (int i=2;i<=n;i++)
    lg2[i]=lg2[i>>1]+1;

    h=lg2[n];

    while (!st.empty()) st.pop();
    a[n+1]=oo;
    st.push(n+1);

    for (int i=n;i>=1;i--)
    {
        while (a[i]>a[st.top()]) st.pop();

        u=i+1;
        v=st.top()-1;

        v=get(t,1,1,n)+a[i];
        u=i;
        update(ma_ans,1,1,n);

        p[i][0]=st.top();

        st.push(i);
    }

    p[n+1][0]=n+1;
    for (int j=1;j<=h;j++)
    for (int i=1;i<=n+1;i++)
    p[i][j]=p[p[i][j-1]][j-1];
}

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];

    build(t,1,1,n);

    BuildSparseTable();

    while (request--)
    {
        cin >> l >> r >> k;

        ok=1;
        for (int j=h;j>=0;j--)
        if (p[l][j]<=r)
        {
            u=l;
            v=p[l][j]-1;
            if (get(ma_ans,1,1,n)>k)
            {
                ok=0;
                break;
            }

            l=p[l][j];
        }

        u=l+1;
        v=r;
        if (ok and get(t,1,1,n)+a[l]>k) ok=0;

        cout << ok << '\n';
    }
}

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