oj.uz

Submission #1071271

# Submission time Handle Problem Language Result Execution time Memory
1071271 2024-08-23T06:27:30 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 102 ms 34316 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n";
const int N = 4e6 + 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 ) ,max({s , d , c }) };
    }
    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(max(h.first , h.second)<=k ){
            cout <<1 << nn
        }
        else cout << 0 << nn
    }
}

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4444 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 102 ms 34316 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4444 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 -