제출 #1156312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156312		Muhammad_Aneeq	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	30 / 100	3095 ms	174504 KiB

sortbooks

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#warning check the output
using namespace std;
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--;
        if (k<getm(l,r))
        {
            if (l==r||pre[r]-pre[l]==r-l)
            {
                cout<<1<<endl;
            }
            else
                cout<<0<<endl;
            continue;
        }
        vector<int>g;
        for (int i=l;i<=r;i++)
            g.push_back(w[i]);
        bool w=1;
        set<int>s;
        while (g.size())
        {
            auto f=s.lower_bound(g.back());
            if (f!=s.begin())
            {
                f--;
                w=(w&(*f+g.back())<=k);
            }
            s.insert(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();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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