Submission #1071340

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

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n";
const int N = 1e6 + 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 ){
        mx[v] = w[l];
      //  cout << l << ' ' << r << ' '<< v << ' ' << 0 << ' '<< w[l]<< nn
        return;
    }
    int mid = ( l + r )/2  ;
    build(v * 2 , l , mid );
    build(v * 2 + 1, mid + 1, r );
    int a = mx[v*2] , b = mx[v*2+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 );
   // cout << l << ' ' << r <<  ' ' << v <<  ' ' << mxs[v]<< ' ' << mx[v]<< nn
}
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);
    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)};
}
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 ;
        if( l == r ){
            cout << 1 << nn
            continue;
        }
        pair<int , int >h = get(1 , l , r , 1 , n );
        cout << h.first << ' ' << h.second <<  ' ' ;
        if(h.first<=k ){
            cout <<1 << nn
        }
        else cout << 0 << nn
    }
}
//8 2
//8 5 1 3 2 9 2 4
//1 2 2
//3 4 0

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