oj.uz

Submission #1071334

# Submission time Handle Problem Language Result Execution time Memory
1071334 2024-08-23T06:45:17 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 735 ms 53988 KB 
#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 ){
        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 ;
        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.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 Incorrect 735 ms 53988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 9552 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 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 -