Submission #1180809

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

sortbooks

// It's the evening of another day. And the end of mine...
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp> \
#include<ext/pb_ds/tree_policy.hpp> \
using namespace __gnu_pbds; \
template<class T> \
using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statisticslmode_update>;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
string sp=" ";
#define F ୨୧
#define fr first
#define er erase
#define sc second
#define in insert
#define ll long long
#define pb push_back
#define mkp make_pair
#define qll queue<ll>
#define dqll deque<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define pll pair<ll,ll>
#define ull unsigned ll
#define mne min_element
#define mxe max_element
#define rs(x)resize(x)
#define vpll vector<pll>
#define vvll vector<vll>
#define pq priority_queue
#define len(x)(ll)x.size()
#define lcm(x,y)x/__gcd(x,y)*y
#define all(x)x.begin(),x.end()
#define umll unordered_map<ll,ll>
#define lg2(x)(63ll-__builtin_clzll(x))
#define precision(x)fixed<<setprecision(x)
#define popcnt(x)(ll)__builtin_popcountll(x)
template<typename t1,typename t2>istream&operator>>(istream&is,pair<t1,t2>&x){return is>>x.fr>>x.sc;}
template<typename t1,typename t2>ostream&operator<<(ostream&os,pair<t1,t2>&x){return os<<x.fr<<' '<<x.sc;}
template<typename t1>istream&operator>>(istream&is,vector<t1>&vc){for(t1&j:vc)is>>j;return is;}
template<typename t1>ostream&operator<<(ostream&os,vector<t1>&vc){for(t1&j:vc)os<<j<<sp;return os;}
// #define ll int_fast32_t
// #define ll int_fast64_t
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
const ll INF=1e9;
const ll INFL=1e18;
const ll MOD=1e9+7;
// const ll MOD=998244353;
const ll maxn=2e5+5;
ll n,m,k=0;
inline void prc(){}
template<typename T>
struct Sparse{
    ll log,lm;
    vector<vector<T>> st;
    // numune:
    // Sparse<ll>mp(n, [&](auto a, auto b){ return min(a, b); });
    function<T(const T&,const T&)> op;
    Sparse(ll lm,function<T(const T&,const T&)> op):lm(lm),op(op){
        log=lg2(lm);
        st.resize(log+1,vector<T>(lm));
    }
    void build(vector<T>&vc){
        for(ll i=0;i<lm;i++)st[0][i]=vc[i];
        for(ll i=1;i<=log;i++){
            for(ll j=0;j+(1<<i)<=lm;j++){
                st[i][j]=op(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    T query(ll l,ll r){
        ll k=lg2(r-l+1);
        return op(st[k][l],st[k][r-(1<<k)+1]);
    }
};
void _(ll&tt){
    cin>>n>>m;
    vpll v(n+1);
    for(ll i=1,x;i<=n;i++) cin>>x, v[i] = {x, i};
    Sparse<pll>mn(n+1, [&](auto a, auto b){
        if(a.fr <= b.fr) return a;
        return b;
    });
    Sparse<pll>mx(n+1, [&](auto a, auto b){
        if(a.fr > b.fr) return a;
        return b;
    });
    mn.build(v), mx.build(v);
    for(ll i=0,a,b,c;i<m;i++){
        cin>>a>>b>>c;
        while(a <= b and mn.query(a, b).sc == a) a ++;
        while(a <= b and mx.query(a, b).sc == b) b --;
        if(a > b){
            cout<<1<<'\n';
            continue;
        }
        ll mxi = mx.query(a, b).sc;
        ll mx2i = mx.query(mxi+1, b).sc;
        if(v[mxi].fr + v[mx2i].fr > c) cout<<0<<'\n';
        else cout<<1<<'\n';
    }
}
signed main(){
    clock_t testcaseruntime=clock();
    cin.tie(0)->sync_with_stdio(0);
    prc();
    ll t=1;
    // cin>>t;
    for(ll tt=1;tt<=t;tt++){
        // cout<<"Case "<<tt<<": ";
        _(tt);
    }
    cerr<<"\n\033[1;31mTime: \033[1;30m"<<(double)(clock()-testcaseruntime)/CLOCKS_PER_SEC<<"\033[1;32m seconds"<<'\n';
}

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