Submission #1294566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294566		k12_khoi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	898 ms	268592 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,l,r,k;
int a[N],lg2[N],ma[N][K],p[N][K],sp_ma[N][K];
bool ok;
stack <int> st;

int Sparse_getmax(int l,int r)
{
    if (l>r) return -oo;

    int z=lg2[r-l+1];

    return max(ma[l][z],ma[r-(1<<z)+1][z]);
}

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

    h=lg2[n];
    for (int j=1;j<=h;j++)
    for (int i=1;i+(1<<j)-1<=n;i++)
    ma[i][j]=max(ma[i][j-1],ma[i+(1<<j-1)][j-1]);

    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();

        sp_ma[i][0]=Sparse_getmax(i+1,st.top()-1)+a[i];
        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];
        sp_ma[i][j]=max(sp_ma[i][j-1],sp_ma[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];
        ma[i][0]=a[i];
    }

    BuildSparseTable();

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

        ok=1;
        for (int j=h;j>=0;j--)
        if (p[l][j]<=r)
        {
            if (sp_ma[l][j]>k)
            {
                ok=0;
                break;
            }

            l=p[l][j];
        }

        if (ok and Sparse_getmax(l+1,r)+a[l]>k) ok=0;

        cout << ok << '\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