Submission #951381

#	Time	Username	Problem	Language	Result	Execution time	Memory
951381		nguyennh	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	930 ms	262144 KiB

sortbooks

#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[3 * 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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23