Submission #1283626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283626		quan606303	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2060 ms	260864 KiB

sortbooks

/*
 * @Author: RMQuan 
 * @Date: 2025-10-26 23:06:34 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-27 01:24:44
 */
/*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 a[maxn],n,q;
struct ST {
    int N;
    vector<vector<int>> st1; // sorted
    vector<int> st2, mx;     // mx = max trên đoạn
    ST(int _n):N(_n),st1(4*_n+5),st2(4*_n+5,0),mx(4*_n+5,0){}

    void Merge(int &ansL, vector<int>& L, int &ansR, vector<int>& R,
               vector<int>& cur, int &ansCur) {
        ansCur = max(ansL, ansR);
        if (!L.empty() && !R.empty()) {
            auto it = lower_bound(R.begin(), R.end(), L.back());
            if (it != R.begin()) { --it; ansCur = max(ansCur, L.back() + *it); }
        }
        cur.reserve(L.size() + R.size());
        int i=0,j=0;
        while (i<(int)L.size() && j<(int)R.size())
            cur.push_back(L[i] < R[j] ? L[i++] : R[j++]);
        while (i<(int)L.size()) cur.push_back(L[i++]);
        while (j<(int)R.size()) cur.push_back(R[j++]);
    }

    void build(int id,int l,int r){
        if (l==r){ st1[id].push_back(a[l]); st2[id]=0; mx[id]=a[l]; return; }
        int mid=(l+r)>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        Merge(st2[id<<1],st1[id<<1],st2[id<<1|1],st1[id<<1|1],st1[id],st2[id]);
        mx[id] = max(mx[id<<1], mx[id<<1|1]);
    }

    inline bool maxLess(const vector<int>& v, int x, int &val){
        auto it = lower_bound(v.begin(), v.end(), x);
        if (it == v.begin()) return false;
        --it; val = *it; return true;
    }

    void get(int id,int l,int r,int u,int v,int &pv,int &ans){
        if (l>v || r<u) return;
        if (l>=u && r<=v){
            if (pv!=-1){ int t; if (maxLess(st1[id], pv, t)) ans = max(ans, pv + t); }
            ans = max(ans, st2[id]);
            pv = max(pv, mx[id]);
            return;
        }
        int mid=(l+r)>>1;
        get(id<<1, l, mid, u, v, pv, ans);
        get(id<<1|1, mid+1, r, u, v, pv, ans);
    }
};

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];
    ST st(n);
    st.build(1,1,n);
    while (q--)
    {
        int u,v,k;
        cin>>u>>v>>k;
        int ans=0;
        int pv=0;
        st.get(1,1,n,u,v,pv,ans);
        cout<<(ans<=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:86:5: note: in expansion of macro 'file'
   86 |     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:86:5: note: in expansion of macro 'file'
   86 |     file();
      |     ^~~~

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