oj.uz

Submission #951382

# Submission time Handle Problem Language Result Execution time Memory
951382 2024-03-21T19:03:02 Z nguyennh Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 913 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[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 21 ms 94808 KB Output is correct
2 Correct 24 ms 94812 KB Output is correct
3 Correct 22 ms 94928 KB Output is correct
4 Correct 22 ms 94812 KB Output is correct
5 Correct 22 ms 94944 KB Output is correct
6 Correct 46 ms 95004 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 39 ms 94808 KB Output is correct
9 Correct 28 ms 95028 KB Output is correct
10 Correct 36 ms 94864 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 94808 KB Output is correct
2 Correct 24 ms 94812 KB Output is correct
3 Correct 22 ms 94928 KB Output is correct
4 Correct 22 ms 94812 KB Output is correct
5 Correct 22 ms 94944 KB Output is correct
6 Correct 46 ms 95004 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 39 ms 94808 KB Output is correct
9 Correct 28 ms 95028 KB Output is correct
10 Correct 36 ms 94864 KB Output is correct
11 Correct 28 ms 95060 KB Output is correct
12 Correct 39 ms 94812 KB Output is correct
13 Correct 42 ms 94812 KB Output is correct
14 Correct 56 ms 95036 KB Output is correct
15 Correct 56 ms 95052 KB Output is correct
16 Correct 86 ms 94812 KB Output is correct
17 Correct 72 ms 95056 KB Output is correct
18 Correct 86 ms 95056 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 468 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 387 ms 124464 KB Output is correct
2 Correct 382 ms 123852 KB Output is correct
3 Correct 412 ms 124616 KB Output is correct
4 Correct 359 ms 123856 KB Output is correct
5 Correct 355 ms 124104 KB Output is correct
6 Correct 361 ms 123984 KB Output is correct
7 Correct 366 ms 124224 KB Output is correct
8 Correct 275 ms 124108 KB Output is correct
9 Correct 76 ms 110684 KB Output is correct
10 Correct 280 ms 123960 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 94808 KB Output is correct
2 Correct 24 ms 94812 KB Output is correct
3 Correct 22 ms 94928 KB Output is correct
4 Correct 22 ms 94812 KB Output is correct
5 Correct 22 ms 94944 KB Output is correct
6 Correct 46 ms 95004 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 39 ms 94808 KB Output is correct
9 Correct 28 ms 95028 KB Output is correct
10 Correct 36 ms 94864 KB Output is correct
11 Correct 28 ms 95060 KB Output is correct
12 Correct 39 ms 94812 KB Output is correct
13 Correct 42 ms 94812 KB Output is correct
14 Correct 56 ms 95036 KB Output is correct
15 Correct 56 ms 95052 KB Output is correct
16 Correct 86 ms 94812 KB Output is correct
17 Correct 72 ms 95056 KB Output is correct
18 Correct 86 ms 95056 KB Output is correct
19 Correct 913 ms 140152 KB Output is correct
20 Correct 899 ms 140308 KB Output is correct
21 Correct 830 ms 140388 KB Output is correct
22 Correct 913 ms 140488 KB Output is correct
23 Correct 832 ms 140228 KB Output is correct
24 Correct 805 ms 140220 KB Output is correct
25 Correct 793 ms 140376 KB Output is correct
26 Correct 849 ms 140364 KB Output is correct
27 Correct 857 ms 140384 KB Output is correct
28 Correct 900 ms 140196 KB Output is correct
29 Correct 843 ms 140320 KB Output is correct
30 Correct 837 ms 140140 KB Output is correct
31 Correct 859 ms 140456 KB Output is correct
32 Correct 843 ms 140740 KB Output is correct
33 Correct 866 ms 140444 KB Output is correct
34 Correct 793 ms 140356 KB Output is correct
35 Correct 816 ms 140560 KB Output is correct
36 Correct 790 ms 140300 KB Output is correct
37 Correct 790 ms 140820 KB Output is correct
38 Correct 808 ms 140464 KB Output is correct
39 Correct 738 ms 140612 KB Output is correct
40 Correct 425 ms 126884 KB Output is correct
41 Correct 688 ms 140228 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 94808 KB Output is correct
2 Correct 24 ms 94812 KB Output is correct
3 Correct 22 ms 94928 KB Output is correct
4 Correct 22 ms 94812 KB Output is correct
5 Correct 22 ms 94944 KB Output is correct
6 Correct 46 ms 95004 KB Output is correct
7 Correct 41 ms 94812 KB Output is correct
8 Correct 39 ms 94808 KB Output is correct
9 Correct 28 ms 95028 KB Output is correct
10 Correct 36 ms 94864 KB Output is correct
11 Correct 28 ms 95060 KB Output is correct
12 Correct 39 ms 94812 KB Output is correct
13 Correct 42 ms 94812 KB Output is correct
14 Correct 56 ms 95036 KB Output is correct
15 Correct 56 ms 95052 KB Output is correct
16 Correct 86 ms 94812 KB Output is correct
17 Correct 72 ms 95056 KB Output is correct
18 Correct 86 ms 95056 KB Output is correct
19 Runtime error 468 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -