oj.uz

Submission #951380

# Submission time Handle Problem Language Result Execution time Memory
951380 2024-03-21T19:00:02 Z nguyennh Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 938 ms 262144 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;

const int inf = numeric_limits<int>::max();

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 merge_sort_tree{
    #define lt(x) (x << 1)
    #define rt(x) (x << 1 | 1)
    vector<int> st[4 * MN];
    
    void build(int id , int l , int r){
      if (l == r){
        st[id].push_back(a[l]);
        return;
      }
      int mid = l + r >> 1;
      build(id << 1 , l , mid);
      build(id << 1 | 1 , mid + 1 , r);
      merge(st[lt(id)].begin() , st[lt(id)].end() , st[rt(id)].begin() , st[rt(id)].end() , back_inserter(st[id]));
    }
    
    int get(int id , int l , int r , int tl , int tr , int x){
      if (l > tr || r < tl) return -inf;
      else if (l >= tl && r <= tr){
        auto it = lower_bound(st[id].begin() , st[id].end() , x) - st[id].begin() - 1;
        if (it >= 0) return st[id][it];
        else return -inf;
      }
      int mid = l + r >> 1;
      return max(get(id << 1 , l , mid , tl , tr , x) , get(id << 1 | 1 , mid + 1 , r , tl , tr , x));
    }
  } mt;
  
  struct Segtri{
    struct Node{
      int l , r , best , max_val;
    };
    
    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);
      int cur = mt.get(1 , 1 , n , y.l , y.r , x.max_val);
      c.best = max(c.best , x.max_val + cur);
      return c;
    }
    
    Node st[4 * MN];
    
    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(){
    mt.build(1 , 1 , n);
    Segtri it;
    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 (){
//  freopen("sortbook.inp" , "r" , stdin);
//  freopen("sortbook.out" , "w" , stdout);
  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::merge_sort_tree::build(int, int, int)':
sortbooks.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |       int mid = l + r >> 1;
      |                 ~~^~~
sortbooks.cpp: In member function 'int sub_final::merge_sort_tree::get(int, int, int, int, int, int)':
sortbooks.cpp:79:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |       int mid = l + r >> 1;
      |                 ~~^~~
sortbooks.cpp: In member function 'void sub_final::Segtri::build(int, int, int)':
sortbooks.cpp:107:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |       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:116:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94864 KB Output is correct
2 Correct 22 ms 94812 KB Output is correct
3 Correct 24 ms 94812 KB Output is correct
4 Correct 25 ms 94812 KB Output is correct
5 Correct 21 ms 95028 KB Output is correct
6 Correct 41 ms 94984 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 40 ms 94812 KB Output is correct
9 Correct 27 ms 94812 KB Output is correct
10 Correct 42 ms 95008 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94864 KB Output is correct
2 Correct 22 ms 94812 KB Output is correct
3 Correct 24 ms 94812 KB Output is correct
4 Correct 25 ms 94812 KB Output is correct
5 Correct 21 ms 95028 KB Output is correct
6 Correct 41 ms 94984 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 40 ms 94812 KB Output is correct
9 Correct 27 ms 94812 KB Output is correct
10 Correct 42 ms 95008 KB Output is correct
11 Correct 28 ms 94808 KB Output is correct
12 Correct 39 ms 94936 KB Output is correct
13 Correct 44 ms 95024 KB Output is correct
14 Correct 57 ms 95048 KB Output is correct
15 Correct 57 ms 94812 KB Output is correct
16 Correct 85 ms 95060 KB Output is correct
17 Correct 72 ms 95052 KB Output is correct
18 Correct 88 ms 95300 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 171020 KB Output is correct
2 Correct 416 ms 171024 KB Output is correct
3 Correct 431 ms 171220 KB Output is correct
4 Correct 379 ms 170824 KB Output is correct
5 Correct 408 ms 171024 KB Output is correct
6 Correct 420 ms 171496 KB Output is correct
7 Correct 394 ms 170956 KB Output is correct
8 Correct 330 ms 171176 KB Output is correct
9 Correct 102 ms 157756 KB Output is correct
10 Correct 290 ms 170952 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94864 KB Output is correct
2 Correct 22 ms 94812 KB Output is correct
3 Correct 24 ms 94812 KB Output is correct
4 Correct 25 ms 94812 KB Output is correct
5 Correct 21 ms 95028 KB Output is correct
6 Correct 41 ms 94984 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 40 ms 94812 KB Output is correct
9 Correct 27 ms 94812 KB Output is correct
10 Correct 42 ms 95008 KB Output is correct
11 Correct 28 ms 94808 KB Output is correct
12 Correct 39 ms 94936 KB Output is correct
13 Correct 44 ms 95024 KB Output is correct
14 Correct 57 ms 95048 KB Output is correct
15 Correct 57 ms 94812 KB Output is correct
16 Correct 85 ms 95060 KB Output is correct
17 Correct 72 ms 95052 KB Output is correct
18 Correct 88 ms 95300 KB Output is correct
19 Correct 938 ms 187080 KB Output is correct
20 Correct 935 ms 187512 KB Output is correct
21 Correct 889 ms 187336 KB Output is correct
22 Correct 873 ms 187492 KB Output is correct
23 Correct 898 ms 187260 KB Output is correct
24 Correct 824 ms 187648 KB Output is correct
25 Correct 809 ms 187384 KB Output is correct
26 Correct 905 ms 187316 KB Output is correct
27 Correct 897 ms 187260 KB Output is correct
28 Correct 890 ms 187496 KB Output is correct
29 Correct 906 ms 187336 KB Output is correct
30 Correct 864 ms 187376 KB Output is correct
31 Correct 877 ms 187604 KB Output is correct
32 Correct 912 ms 187188 KB Output is correct
33 Correct 907 ms 187316 KB Output is correct
34 Correct 814 ms 187320 KB Output is correct
35 Correct 826 ms 187212 KB Output is correct
36 Correct 830 ms 187168 KB Output is correct
37 Correct 828 ms 187160 KB Output is correct
38 Correct 812 ms 187492 KB Output is correct
39 Correct 752 ms 187340 KB Output is correct
40 Correct 452 ms 173740 KB Output is correct
41 Correct 693 ms 187332 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94864 KB Output is correct
2 Correct 22 ms 94812 KB Output is correct
3 Correct 24 ms 94812 KB Output is correct
4 Correct 25 ms 94812 KB Output is correct
5 Correct 21 ms 95028 KB Output is correct
6 Correct 41 ms 94984 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 40 ms 94812 KB Output is correct
9 Correct 27 ms 94812 KB Output is correct
10 Correct 42 ms 95008 KB Output is correct
11 Correct 28 ms 94808 KB Output is correct
12 Correct 39 ms 94936 KB Output is correct
13 Correct 44 ms 95024 KB Output is correct
14 Correct 57 ms 95048 KB Output is correct
15 Correct 57 ms 94812 KB Output is correct
16 Correct 85 ms 95060 KB Output is correct
17 Correct 72 ms 95052 KB Output is correct
18 Correct 88 ms 95300 KB Output is correct
19 Runtime error 325 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -