Submission #1136087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136087		SSSM	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	8 / 100	3103 ms	327680 KiB

sortbooks

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

#define SZ(a) (ll)a.size()
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define md(a) (a%mod+mod)%mod
#define lc (id<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;

const ll maxn=1e6+5, LOG=30, mod=1e9+7, INF=1e18;

struct Node{
    ll ans, mx;
    set<ll> st;
    Node(ll ans_, ll mx_, set<ll> st_)
    {
        ans=ans_;
        mx=mx_;
        st=st_;
    }
    Node () {};

} seg[maxn<<2];
ll n, q, A[maxn];

Node Merge(Node L, Node R)
{
    ll mx=max(L.mx, R.mx);
    set<ll> st;
    for(ll j:L.st) st.insert(j);
    for(ll j:R.st) st.insert(j);
    ll ans=max(L.ans, R.ans);
    auto t=R.st.lower_bound(L.mx);
    if(t!=R.st.begin()) ans=max(ans, L.mx+(*prev(t)));
    return Node(ans, mx, st);
}

void Build(ll l=1, ll r=n+1, ll id=1)
{
    if(l==r-1)
    {
        seg[id]=Node(0, A[l], set<ll>{A[l]});
        return;
    }
    Build(l, mid, lc);
    Build(mid, r, rc);
    seg[id]=Merge(seg[lc], seg[rc]);
}

Node Get(ll s, ll e, ll l=1, ll r=n+1, ll id=1)
{
    if(l>=e || r<=s) return Node(0, 0, set<ll>{});
    if(s<=l && r<=e) return seg[id];
    return Merge(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>q;
    for(ll i=1;i<=n;i++) cin>>A[i];
    Build();
    while(q--)
    {
        ll l, r, k;
        cin>>l>>r>>k;
        Node nd=Get(l, r+1);
        if(nd.ans<=k) cout<<1<<"\n";
        else cout<<"0\n";
    }
}

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