Submission #1131168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131168		Gray	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2791 ms	260872 KiB

sortbooks

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = INT_MAX;
const ll MOD = 1e9+7;

struct seg_tree{
    struct node{
        vector<ll> vals;
        ll res;
    };
    vector<node> t;
    ll sz, rsz;
    seg_tree(ll N){
        sz=N*4; rsz=N;
        t.resize(sz);
    }

    void build(ll tl, ll tr, ll v, vector<ll> &a){
        if (tl==tr){
            t[v].vals.push_back(a[tl]);
            t[v].res=0;
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2, a);
            build(tm+1, tr, v*2+1, a);
            // cout << "SYATY" << endl;
            assert(!(t[v*2].vals.empty() or t[v*2+1].vals.empty()));
            t[v].vals.resize(tr-tl+1);
            merge(t[v*2].vals.begin(), t[v*2].vals.end(), t[v*2+1].vals.begin(), t[v*2+1].vals.end(), t[v].vals.begin());
            // cout << "EDN" << endl;
            assert((ll)t[v].vals.size()==(tr-tl+1));
            t[v].res=max(t[v*2].res, t[v*2+1].res);
            ll ind = lower_bound(t[v*2+1].vals.begin(), t[v*2+1].vals.end(), t[v*2].vals.back())-t[v*2+1].vals.begin();
            t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0));
        }
    }

    pair<ll, ll> query(ll tl, ll tr, ll v, ll l, ll r, ll pass_mx){
        // cout << tl << "-" << tr << ln;
        if (l>r) return {-INF, pass_mx};
        else if (tl==l and tr==r){
            // cout << tl << "-" << tr << "->" <<  t[v].res << ln;
            if (pass_mx==-INF) return {t[v].res, t[v].vals.back()};
            else{
                ll ind = lower_bound(t[v].vals.begin(), t[v].vals.end(), pass_mx)-t[v].vals.begin();
                ll res = max(t[v].res, (ind-1>=0?pass_mx+t[v].vals[ind-1]:0));
                // cout << tl << "-" << tr << " : " << ind << "->" << (ind-1>=0?pass_mx+t[v].vals[ind-1]:0) << ln;
                return {res, max(pass_mx, t[v].vals.back())};
            }
        }else{
            ll tm = (tl+tr)/2;
            pair<ll, ll> res1 = query(tl, tm, v*2, l, min(r, tm), pass_mx);
            pass_mx=res1.ss;
            pair<ll, ll> res2 = query(tm+1, tr, v*2+1, max(l, tm+1), r, pass_mx);
            return {max(res1.ff, res2.ff), res2.ss};
        }
    }

    void build(vector<ll> &a){
        build(0, rsz-1, 1, a);
    }

    ll query(ll l, ll r){
        // cout << "Start" << endl;
        ll res= query(0, rsz-1, 1, l, r, -INF).ff;
        // cout << "End" << endl;
        return res;
    }
};



void solve(){
    ll n, m; cin >> n >> m;
    vector<ll> a(n);
    for (ll i=0; i<n; i++) cin >> a[i];
    seg_tree tr(n);
    tr.build(a);
    // return;
    while (m--){
        ll l, r, k; cin >> l >> r >> k;
        l--; r--;
        ll res = tr.query(l, r);
        // cout << res << " -> ";
        if (res>k){
            cout << 0 << ln;
        }else{
            cout << 1 << ln;
        }
    }
}
/*
6 8 7 9 7.5

*/
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t >> n;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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