oj.uz

Submission #1071353

# Submission time Handle Problem Language Result Execution time Memory
1071353 2024-08-23T06:51:21 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 54 ms 10836 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n";
const int N = 4e5 + 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);
    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 ;
        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

Compilation message

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:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 10836 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 7760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -