Submission #1156287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156287		Muhammad_Aneeq	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	518 ms	327680 KiB

sortbooks

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#warning check the output
using namespace std;
#define int long long
int const N=1e6+10,LG=20;
int w[N]={},pre[N]={};
int mx[N][LG],mn[N][LG]={};
int n,m;
void build()
{
    for (int i=0;i<n;i++)
        mx[i][0]=mn[i][0]=w[i];
    for (int i=1;(1<<i)<=n;i++)
    {
        for (int j=0;j+(1<<i)<=n;j++)
        {
            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
            mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]);
        }
    }
}
int getx(int l,int r)
{
    int lg=log2(r-l+1);
    return max(mx[l][lg],mx[r-(1<<lg)+1][lg]);
}
int getm(int l,int r)
{
    int lg=log2(r-l+1);
    return min(mn[l][lg],mn[r-(1<<lg)+1][lg]);
}
inline void solve()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
        cin>>w[i];
    build();
    for (int i=1;i<n;i++)
        pre[i]=pre[i-1]+(w[i-1]<=w[i]);
    while (m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        l--;r--;
        if (l==r)
        {
            cout<<1<<endl;
            continue;
        }
        int st=1,en=(r-l+1)+1;
        while (st+1<en)
        {
            int mid=(st+en)/2;
            if (pre[r-1]-pre[r-mid]==mid-1)
                st=mid;
            else
                en=mid;
        }
        int z=r-st;
        if (z<=l)
        {
            cout<<1<<endl;continue;
        }
        int g=getm(l,r)+getx(l,z);
        if (g>k)
            cout<<0<<endl;
        else
            cout<<1<<endl;
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

sortbooks.cpp:11:2: warning: #warning check the output [-Wcpp]
   11 | #warning check the output
      |  ^~~~~~~

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