oj.uz

Submission #951378

# Submission time Handle Problem Language Result Execution time Memory
951378 2024-03-21T18:26:08 Z nguyennh Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 928 ms 63952 KB 
#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

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

const int MN = 2e5 + 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 () {};
      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);
      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;
    }
    
    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(){
    mt.build(1 , 1 , n);
    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 (){
//  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:111:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |       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:120:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 9 ms 19036 KB Output is correct
5 Correct 5 ms 19256 KB Output is correct
6 Correct 30 ms 19228 KB Output is correct
7 Correct 25 ms 19032 KB Output is correct
8 Correct 31 ms 19232 KB Output is correct
9 Correct 11 ms 19032 KB Output is correct
10 Correct 27 ms 19252 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 9 ms 19036 KB Output is correct
5 Correct 5 ms 19256 KB Output is correct
6 Correct 30 ms 19228 KB Output is correct
7 Correct 25 ms 19032 KB Output is correct
8 Correct 31 ms 19232 KB Output is correct
9 Correct 11 ms 19032 KB Output is correct
10 Correct 27 ms 19252 KB Output is correct
11 Correct 11 ms 19292 KB Output is correct
12 Correct 22 ms 19292 KB Output is correct
13 Correct 25 ms 19300 KB Output is correct
14 Correct 39 ms 19292 KB Output is correct
15 Correct 40 ms 19288 KB Output is correct
16 Correct 69 ms 19288 KB Output is correct
17 Correct 55 ms 19288 KB Output is correct
18 Correct 69 ms 19296 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 38124 KB Output is correct
2 Correct 363 ms 40140 KB Output is correct
3 Correct 363 ms 39596 KB Output is correct
4 Correct 325 ms 40396 KB Output is correct
5 Correct 307 ms 39004 KB Output is correct
6 Correct 324 ms 40136 KB Output is correct
7 Correct 331 ms 39644 KB Output is correct
8 Correct 248 ms 39296 KB Output is correct
9 Correct 52 ms 20820 KB Output is correct
10 Correct 255 ms 39228 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 9 ms 19036 KB Output is correct
5 Correct 5 ms 19256 KB Output is correct
6 Correct 30 ms 19228 KB Output is correct
7 Correct 25 ms 19032 KB Output is correct
8 Correct 31 ms 19232 KB Output is correct
9 Correct 11 ms 19032 KB Output is correct
10 Correct 27 ms 19252 KB Output is correct
11 Correct 11 ms 19292 KB Output is correct
12 Correct 22 ms 19292 KB Output is correct
13 Correct 25 ms 19300 KB Output is correct
14 Correct 39 ms 19292 KB Output is correct
15 Correct 40 ms 19288 KB Output is correct
16 Correct 69 ms 19288 KB Output is correct
17 Correct 55 ms 19288 KB Output is correct
18 Correct 69 ms 19296 KB Output is correct
19 Correct 877 ms 56692 KB Output is correct
20 Correct 873 ms 56840 KB Output is correct
21 Correct 814 ms 57368 KB Output is correct
22 Correct 801 ms 56264 KB Output is correct
23 Correct 776 ms 57288 KB Output is correct
24 Correct 740 ms 57656 KB Output is correct
25 Correct 761 ms 63776 KB Output is correct
26 Correct 928 ms 62752 KB Output is correct
27 Correct 795 ms 62916 KB Output is correct
28 Correct 893 ms 62828 KB Output is correct
29 Correct 855 ms 63792 KB Output is correct
30 Correct 848 ms 63080 KB Output is correct
31 Correct 820 ms 63232 KB Output is correct
32 Correct 827 ms 63500 KB Output is correct
33 Correct 836 ms 63316 KB Output is correct
34 Correct 733 ms 63952 KB Output is correct
35 Correct 730 ms 62084 KB Output is correct
36 Correct 722 ms 63684 KB Output is correct
37 Correct 753 ms 62764 KB Output is correct
38 Correct 746 ms 62284 KB Output is correct
39 Correct 724 ms 62828 KB Output is correct
40 Correct 417 ms 45828 KB Output is correct
41 Correct 675 ms 62484 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 9 ms 19036 KB Output is correct
5 Correct 5 ms 19256 KB Output is correct
6 Correct 30 ms 19228 KB Output is correct
7 Correct 25 ms 19032 KB Output is correct
8 Correct 31 ms 19232 KB Output is correct
9 Correct 11 ms 19032 KB Output is correct
10 Correct 27 ms 19252 KB Output is correct
11 Correct 11 ms 19292 KB Output is correct
12 Correct 22 ms 19292 KB Output is correct
13 Correct 25 ms 19300 KB Output is correct
14 Correct 39 ms 19292 KB Output is correct
15 Correct 40 ms 19288 KB Output is correct
16 Correct 69 ms 19288 KB Output is correct
17 Correct 55 ms 19288 KB Output is correct
18 Correct 69 ms 19296 KB Output is correct
19 Runtime error 34 ms 40232 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -