oj.uz

Submission #951371

# Submission time Handle Problem Language Result Execution time Memory
951371 2024-03-21T17:45:18 Z nguyennh Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 37548 KB 
#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

const int MN = 1e6 + 5;

int n , m , a[MN];

namespace sub_trau{
  bool valid_input(){
    return n <= 500 && m <= 500;
  }
  
  void solve(){
    while(m--){
      int l , r , k;
      cin >> l >> r >> k;
      int ans = 0;
      for ( int i = l ; i <= r ; i++ ){
        for ( int j = i ; j <= r ; j++ ){
          if (a[j] < a[i]) ans = max(ans , a[j] + a[i]);
        }
      }
      cout << (ans <= k ? 1 : 0) << el;
    }
  }
}

namespace sub2{
  bool valid_input(){
    return n <= 5000 && m <= 5000;
  }
  
  void solve(){
    while(m--){
      int l , r , k;
      cin >> l >> r >> k;
      int ans = 0;
      vector<int> pref(r + 3);
      pref[l - 1] = INT_MIN;
      pref[l] = a[l];
      for ( int i = l + 1 ; i <= r ; i++ ) pref[i] = max(pref[i - 1] , a[i]);
      for ( int i = l ; i <= r ; i++ ){
        if (pref[i - 1] > a[i]) ans = max(ans , a[i] + pref[i - 1]);
      }
      cout << (ans <= k ? 1 : 0) << el;
    }
  }
}

namespace sub_final{
  struct Segtri{
    struct Node{
      int l , r , best , max_val;
      Node () {};
      Node (int _l , int _r , int _b , int _m) : l(_l) , r(_r) , best(_b) , max_val(_m) {};
    };
    
    Node merge(const Node &x , const Node &y){
      Node c;
      c.l = x.l;
      c.r = y.r;
      c.max_val = max(x.max_val , y.max_val);
      c.best = max(x.best , y.best);
      for ( int i = y.l ; i <= y.r ; i++ ){
        if (a[i] < x.max_val) c.best = max(c.best , x.max_val + a[i]);
      }
      return c;
    }
    
    vector<Node> st;
    
    Segtri(int n) : st(4 * n + 5) {};
    
    void build(int id , int l , int r){
      if (l == r){
        st[id] = {l , l , 0 , a[l]};
        return;
      }
      int mid = l + r >> 1;
      build(id << 1 , l , mid);
      build(id << 1 | 1 , mid + 1 , r);
      st[id] = merge(st[id << 1] , st[id << 1 | 1]);
    }
    
    Node get(int id , int l , int r , int tl , int tr){
      if (l >= tl && r <= tr) return st[id];
      else {
        int mid = l + r >> 1;
        if (tl > mid) return get(id << 1 | 1 , mid + 1 , r , tl , tr);
        else if (tr <= mid) return get(id << 1 , l , mid , tl , tr);
        else return merge(get(id << 1 , l , mid , tl , tr) , get(id << 1 | 1 , mid + 1 , r , tl , tr));
      }
    }
  };
  
  void solve(){
    Segtri it(n);
    it.build(1 , 1 , n);
    while(m--){
      int l , r , k;
      cin >> l >> r >> k;
      cout << (it.get(1 , 1 , n , l , r).best <= k ? 1 : 0) << el;
    }
  }
}

int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
  if (sub_trau::valid_input()){
    sub_trau::solve();
    return 0;
  }
  if (sub2::valid_input()){
    sub2::solve();
    return 0;
  }
  sub_final::solve();
}

Compilation message

sortbooks.cpp: In member function 'void sub_final::Segtri::build(int, int, int)':
sortbooks.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |       int mid = l + r >> 1;
      |                 ~~^~~
sortbooks.cpp: In member function 'sub_final::Segtri::Node sub_final::Segtri::get(int, int, int, int, int)':
sortbooks.cpp:91:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 19 ms 348 KB Output is correct
7 Correct 23 ms 356 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 15 ms 472 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 19 ms 348 KB Output is correct
7 Correct 23 ms 356 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 15 ms 472 KB Output is correct
11 Correct 8 ms 348 KB Output is correct
12 Correct 19 ms 520 KB Output is correct
13 Correct 21 ms 348 KB Output is correct
14 Correct 35 ms 348 KB Output is correct
15 Correct 36 ms 524 KB Output is correct
16 Correct 65 ms 348 KB Output is correct
17 Correct 51 ms 520 KB Output is correct
18 Correct 65 ms 344 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 37548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3014 ms 9320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 19 ms 348 KB Output is correct
7 Correct 23 ms 356 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 15 ms 472 KB Output is correct
11 Correct 8 ms 348 KB Output is correct
12 Correct 19 ms 520 KB Output is correct
13 Correct 21 ms 348 KB Output is correct
14 Correct 35 ms 348 KB Output is correct
15 Correct 36 ms 524 KB Output is correct
16 Correct 65 ms 348 KB Output is correct
17 Correct 51 ms 520 KB Output is correct
18 Correct 65 ms 344 KB Output is correct
19 Execution timed out 3062 ms 13784 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 19 ms 348 KB Output is correct
7 Correct 23 ms 356 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 15 ms 472 KB Output is correct
11 Correct 8 ms 348 KB Output is correct
12 Correct 19 ms 520 KB Output is correct
13 Correct 21 ms 348 KB Output is correct
14 Correct 35 ms 348 KB Output is correct
15 Correct 36 ms 524 KB Output is correct
16 Correct 65 ms 348 KB Output is correct
17 Correct 51 ms 520 KB Output is correct
18 Correct 65 ms 344 KB Output is correct
19 Execution timed out 3056 ms 37548 KB Time limit exceeded
20 Halted 0 ms 0 KB -