Submission #1283611

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

sortbooks

/*
 * @Author: RMQuan 
 * @Date: 2025-10-26 23:06:34 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-27 00:41:01
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=1e6+7;
const int inf=1e9;
const int LOG=20;
int mx[maxn][LOG+1];
int a[maxn],n,q;
int get_max(int l,int r)
{
    if (l>r)return 0;
    int k=__lg(r-l+1);
    return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
struct ST
{
    int N;
    vector<vector<int> > st1;
    vector<int> st2;
    ST(int _n):N(_n),st1(4*_n+5,vector<int>(0)),st2(4*_n+5,0){}
    void Merge(int &ans_L,vector<int> &L,int &ans_R,vector<int> &R,vector<int> &cur_node,int &cur_ans)
    {
        cur_ans=max(ans_L,ans_R);
        cur_node;
        if (L.size())for (auto i:R)if (i<L[L.size()-1])cur_ans=max(cur_ans,i+L[L.size()-1]);
        int i=0,j=0;
        while (i<L.size()&&j<R.size())
        {
            if (L[i]<R[j])
            {
                cur_node.push_back(L[i]);
                i++;
            }
            else 
            {
                cur_node.push_back(R[j]);
                j++;
            }
        }
        while(i<L.size())
        {
            cur_node.push_back(L[i]);
            i++;
        }
        while (j<R.size())
        {
            cur_node.push_back(R[j]);
            j++;
        }
    }
    void build(int id,int l,int r)
    {
        if (l==r)
        {
            st1[id].push_back(a[l]);
            st2[id]=0;
            return ;
        }
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        Merge(st2[id*2],st1[id*2],st2[id*2+1],st1[id*2+1],st1[id],st2[id]);
    }
    int get(int id,int l,int r,int u,int v)
    {
        if (l>v||r<u)return 0;
        if (l>=u&&r<=v)
        {
            int pv_mx=get_max(u,l-1);
            int cur_ans=st2[id];
            auto it=lower_bound(st1[id].begin(),st1[id].end(),pv_mx);
            if (it!=st1[id].begin()&&it!=st1[id].end())
            {
                --it;
                cur_ans=max(cur_ans,pv_mx+*it);
            }
            return cur_ans;
        }
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
    
};
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>q;
    for (int i=1;i<=n;i++)cin>>a[i];
    for (int i=1;i<=n;i++)mx[i][0]=a[i];
    for (int j=1;j<=LOG;j++)
    {
        for (int i=1;i+(1<<j)+1<=n;i++)mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
    }
    ST st(n);
    st.build(1,1,n);
    while (q--)
    {
        int u,v,k;
        cin>>u>>v>>k;
        cout<<(st.get(1,1,n,u,v)<=k?1:0)<<endl;
    }
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:24:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:112:5: note: in expansion of macro 'file'
  112 |     file();
      |     ^~~~
sortbooks.cpp:24:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:112:5: note: in expansion of macro 'file'
  112 |     file();
      |     ^~~~

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