Submission #409082

#	Time	Username	Problem	Language	Result	Execution time	Memory
409082		codebuster_10	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KiB

bubblesort2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>   

using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std ;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  #ifdef ONLINE_JUDGE
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
  #define __f(...) 0
  #endif
}

/*
 * Treaps Implementation
  * prior is priority which gives heap property
  * key gives BST property
  * size is size of our tree
  * sum is sum of our subtree
  * lazy is lazy value
  * val is value stored at that node
 * source:
    https://tanujkhattar.wordpress.com/2016/01/10/treaps-one-tree-to-rule-em-all-part-2/
    https://www.codechef.com/viewsolution/36079099
 * verification:
    https://www.spoj.com/status/HORRIBLE,deepkamal/

*/
// currently not considering reverse
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int Random(){
  return uniform_int_distribution<int>(0,1e9)(rng) ;
}

struct node{
    int prior, size, val, sum, lazy, key; 
    //bool rev ;
    node *l, *r;
    node ():l(nullptr) , r(nullptr) {}
};
node* newnode(int k,int _val){
    node *ret ; ret = new node();
    ret->key = k ;
    ret->val = ret->sum = _val;
    ret->lazy = 0 ;
    ret->size = 1 ;
    ret->prior = Random() ;
    return ret ;
}
typedef node* pnode;


struct IMPLICIT_TREAP {

  node *tree;
  IMPLICIT_TREAP(): tree (nullptr) { }

  int SZ(pnode t){
    return t ? t->size : 0 ;
  }

  void upd_sz(pnode t){
    if(t){ t->size = SZ(t->l) + 1 + SZ(t->r); }
  }

  void combine(pnode& t,pnode l,pnode r){//combine segtree ranges
    t->sum = 0 ;
    if(l) t->sum += l->sum ; 
    if(r) t->sum += r->sum;
  }

  void propagate(pnode t){
    if(!t or !t->lazy) return ; // here this implementation is for sum so t->lazy != 0
    t->val += t->lazy ; //operation of lazy
    t->sum += t->lazy * SZ(t) ;
    if(t->l) t->l->lazy += t->lazy ; //propagate lazy for t's children
    if(t->r) t->r->lazy += t->lazy ;
    t->lazy = 0;
  }
  void reset(pnode t){
    if(t) t->sum = t->val;//lazy already propagated
  }
  void operation(pnode t){//operation of segtree
    if(!t) return ;
    reset(t) ; // node represents single element of array
    propagate(t->l) ; propagate(t->r) ;//imp:propagate lazy before combining l,r
    combine(t,t->l,t->r) ; t->sum += t->val ;
  }
  void split(pnode t,pnode &l,pnode &r,int pos,int add = 0){ // add keeps track of the i value
    if(!t){ l = r = NULL ; return ; }
    propagate(t) ; 
    int curr_pos = add + SZ(t->l);
    if(curr_pos <= pos){//element at pos goes to "l"
      split(t->r, t->r, r, pos, curr_pos+1); l = t;
    }else{ 
      split(t->l, l, t->l, pos, add); r = t;
    }
    upd_sz(t) ; operation(t) ;
  }
  void merge(pnode &t,pnode l,pnode r){//result/left/right array
    propagate(l) ; propagate(r) ;
    if(!l or !r){
      t = l?l:r;
    }else if(l->prior > r->prior) {
      merge(l->r,l->r,r); t = l;
    }else{
      merge(r->l,l,r->l); t = r;
    }
    upd_sz(t) ; operation(t) ;
  }
  void insert(int pos,int _val){
    pnode r = newnode(pos,_val);
    pnode a, b, c;
    split(tree, a, b, pos-1) ;
    merge(c, a, r);
    merge(tree, c, b);  
  }
  void del(int pos){
    pnode a, b, c;
    split(tree, a, c, pos);
    split(a, a, b, pos-1);
    merge(tree, a, c);
  }
  int get(int pos){
    pnode a, b, c;
    split(tree, a, c, pos) ; split(a, a, b, pos-1) ;
    merge(a, a, b) ; merge(tree, a, c) ;
    return b->val ;
  }
  void range_update(pnode t,int l,int r,int val){ //[l,r]
    pnode a, b, c;
    split(t, b, c, r) ; split(b, a, b, l-1) ;
    b->lazy += val;
    merge(b,a,b) ; merge(t,b,c) ;
  }
  int range_query(pnode t,int l,int r){//[l,r]
    pnode a, b, c;
    split(t,a,c,r) ; split(a,a,b,l-1) ;
    int ans = b->sum ;
    merge(a,a,b) ; merge(t,a,c) ;
    return ans;
  }
};

struct compress_1d_co_ordinates {
	vector<int> values;
  void add(int x){
  	values.push_back(x);
  }
  void gen(){
  	sort(values.begin(),values.end());
  	values.erase(unique(values.begin(),values.end()),values.end());
  }
  int get(int x){
  	int j = lower_bound(values.begin(),values.end(),x) - values.begin();
  	assert(values[j] == x); return j;
  }
}C;

signed main(){
  setIO() ;
  int n,q; rd(n,q);
  vt<int> a(n);
  rd(a);
  for(auto i : a) C.add(i);
  vt<pr<int,int>> queries;
  while(q--){
  	int i,x; rd(i,x);
  	queries.eb(i,x);
  	C.add(x);
  }
  C.gen();
  for(auto& i : a) i = C.get(i);
  for(auto [i,x]:queries) x = C.get(x);
  
  
}

Compilation message (stderr)

bubblesort2.cpp:8:40: error: 'less' was not declared in this scope; did you mean 'std::less'?
    8 | using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
      |                                        ^~~~
      |                                        std::less
In file included from /usr/include/c++/10/string:48,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_function.h:340:12: note: 'std::less' declared here
  340 |     struct less;
      |            ^~~~
bubblesort2.cpp:8:46: error: template argument 3 is invalid
    8 | using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
      |                                              ^