Submission #1156302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156302		Muhammad_Aneeq	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3097 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=21;
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--;
        vector<int>g;
        for (int i=l;i<=r;i++)
            g.push_back(w[i]);
        sort(begin(g),end(g));
        for (int i=r;i>=l;i--)
        {
            if (g.back()==w[i])
                g.pop_back();
            else
                break;
        }
        bool w=1;
        int mx=-1e9;
        while (g.size())
        {
            w=(w&(g.back()+mx<=k));
            mx=max(mx,g.back());
            g.pop_back();
        }
        cout<<w<<endl;
        // 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