Submission #151408

#	Time	Username	Problem	Language	Result	Execution time	Memory
151408		leatherman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	768 ms	62840 KiB

sortbooks

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define ll int
#define ld long double
#define endl "\n"
#define fi first
#define se second
#define y1 sadjfskldf
#define PB push_back
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

const ll N = 2e5 + 200;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct trees
{
    ll ans;
    vector<ll> val;
};
trees t[4 * N];
ll a[N],global,n,Q,l,r,x,k;
ll quest(ll mx,vector<ll> &v)
{
    ll pos = lower_bound(all(v), mx) - v.begin();
    if(!pos) return 0;
    return mx + v[--pos];
}
void build(ll v,ll tl,ll tr)
{
    if(tl == tr)
    {
        t[v].val.PB(a[tl]);
        return;
    }
    ll tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    for(auto x : t[2 * v].val) t[v].val.PB(x);
    for(auto x : t[2 * v + 1].val) t[v].val.PB(x);
    sort(all(t[v].val));
    t[v].ans = max(max(t[2 * v].ans, t[2 * v + 1].ans), quest((t[2 * v].val).back(), (t[2 * v + 1].val)));
}
ll get(ll v,ll tl,ll tr,ll l, ll r)
{
    if(l > r) return 0;
    if(tl == l && tr == r)
    {
        ll ans = t[v].ans;
        ans = max(ans, quest(global, t[v].val));
        global = max(global, t[v].val.back());
        return ans;
    }
    ll tm = (tl + tr) / 2,x,y;
    x = get(2 * v, tl, tm, l, min(tm, r));
    y = get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    return max(x, y);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>Q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build(1, 1, n);
    while(Q--)
    {
        cin>>l>>r>>k;
        global = 0;
        x = get(1, 1, n, l, r);
        if(x <= k) cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}
/*
8 1
5 4 3 1 6 7 8 2
2 5
*/

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