Submission #1071283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071283		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	73 ms	25428 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n";
const int N = 5e6 + 8  , inf = 1e9+7 ;
int  n , m , q , w[N] ;
int mx[N] , mxs[N];
void build(int v , int l , int r ){
    if(l == r ){
        mxs[v] =0;
        mx[v] = w[l];
        return;
    }
    int mid = ( l + r )>>1  ;
    build(v * 2 , l , mid );
    build(v * 2 + 1, mid + 1, r );
    int a = mx[v*v] , b = mx[v*v+1];
    mxs[v] = max(mxs[v*2] , mxs[v*2+1]);
    if( a > b ){
        mxs[v] = max(mxs[v] , a + b );
    }
    mx[v] = max(a , b );
}
pair<int , int > get(int v , int tl , int tr ,int l , int r  ){
    if( tl <= l && r <= tr ){
        return {mxs[v] , mx[v]};
    }
    if( l > tr || r < tl ){
        return {-1 , -1 };
    }
    int mid = ( l + r )/2;
    pair<int ,int >a = get(v*2  , tl , tr  , l , mid ) , b = get(v*2+1  , tl , tr  , mid+1 , r );
    if(a.second> -1 && b.second> -1 ){
        int c = a.first, d = b.first;
        int s =  0 ;
        if( a.second > b.second  ){
            s = a.second + b.second ;
        }
        return {max({c , d  , s }) ,max(a.second , b.second ) };
    }
    else if(a.second > -1 ){
        return a ;
    }
    else if(b.second > -1 ){
        return b ;
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>> n >> q;
    for(int i  = 1; i <= n; i++){
        cin>> w[i];
    }
    build(1 , 1 , n );
    while(q--){
        int l , r , k  ;
        cin>> l >> r >> k ;
        pair<int , int >h = get(1 , l , r , 1 , n );
        if(h.first<=k ){
            cout <<1 << nn
        }
        else cout << 0 << nn
    }
}
//5 2
//3 5 1 8 2
//1 3 6
//2 5 3

Compilation message (stderr)

sortbooks.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^

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