Submission #1172139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172139		Hurryup_7735	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	138 ms	14156 KiB

sortbooks

//In The Name Of ALLAH!
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
#define endl '\n'
#define pb push_back
#define pf push_front
#define speedyboy ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define bpc __builtin_popcount
#define all(x) x.begin() , x.end()
#define allr(x) x.rbegin() , x.rend()
#define F first
#define S second
#define pll pair<ll , ll>
#define turtle tuple<ll , ll , ll , ll>
#define pss pair<string , string>
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define ordered_set tree<ll , null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update>


const ll sz = 2e5 + 5 , INF = 1e18 ,  MOD = 998244353;
ll a[sz] , st[sz<<2] , res[sz];

void update(ll l , ll r , ll in , ll x , ll val){
    if(x < l || r < x) return;
    if(l == r){
        st[in] = val;
        return;
    }
    ll mid = (l + r)>>1;
    update(l , mid , in<<1 , x , val);
    update(mid + 1 , r , in<<1|1 , x , val);
    st[in] = max(st[in<<1] , st[in<<1|1]);
}

ll getans(ll a , ll b , ll l , ll r , ll in){
    if(a > r || l > b) return -INF;
    if(a <= l && r <= b) return st[in];
    ll mid = (l + r)>>1;
    return max(getans(a , b , l , mid , in<<1) , getans(a , b , mid + 1 , r , in<<1|1));
}

ll mask , i , j , o;
void solve(){
    ll n , q;
    cin >> n >> q;
    for(i = 1 ; i <= n ; i++) cin >> a[i];
    vector<array<ll , 4>> v(q);
    for(i = 0 ; i < q ; i++){
        cin >> v[i][1] >> v[i][0] >> v[i][2];
        v[i][3] = i;
    }
    sort(all(v));
    stack<ll> s;
    ll last = 0;
    for(i = 0 ; i < q ; i++){
        ll r = v[i][0] , l = v[i][1] , k = v[i][2] , ind = v[i][3];
        if(last < r){
            for(j = last + 1 ; j <= r ; j++){
                while(!s.empty() && a[s.top()] <= a[j]) s.pop();
                if(!s.empty()){
                    ll x = s.top();
                    update(1 , n , 1 , x , a[j] + a[x]);
                }
                s.push(j);
            }
            last = r;
        }
        ll ans = getans(l , r , 1 , n , 1);
        res[ind] = (ans > k ? 0 : 1);
    }
    for(i = 0 ; i < q ; i++) cout << res[i] << endl;
}

signed main(){
    speedyboy;
    //open;
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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