Submission #409144

#	Time	Username	Problem	Language	Result	Execution time	Memory
409144		codebuster_10	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	5 ms	972 KiB

bubblesort2

#include <bits/stdc++.h>


using namespace std ;

#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>;

#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

// confirmed for max as well as min.

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, mx, mn, 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->mx = ret->mn = _val;
    ret->lazy = 0 ;
    ret->size = 1 ;
    ret->prior = Random() ;
    return ret ;
}
typedef node* pnode;

const int inf = 1e15;
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->mx = -inf, t->mn = inf;
    if(l) ckmax(t->mx,l->mx),ckmin(t->mn,l->mn); 
    if(r)	ckmax(t->mx,r->mx),ckmin(t->mn,r->mn); 
  }

  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->mn += t->lazy;
    t->mx += t->lazy;
    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->mn = t->mx = 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) ; ckmax(t->mx,t->val),ckmin(t->mn,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(int l,int r,int val){ //[l,r]
    pnode a, b, c;
    split(tree, b, c, r) ; split(b, a, b, l-1) ;
    b->lazy += val;
    merge(b,a,b) ; merge(tree,b,c) ;
  }
  int range_query(int l,int r){//[l,r]
    pnode a, b, c;
    split(tree,a,c,r) ; split(a,a,b,l-1) ;
    int ans = max(b->mx,int(-1)*b->mn);
    merge(a,a,b) ; merge(tree,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;
const int LOG = 25;

#undef int
std::vector<int> countScans(std::vector<int> _A,std::vector<int> _X,std::vector<int> _V){
#define int int64_t
 
  setIO() ;
  int n = sz(_A), q = sz(_X); //rd(n,q);
  vt<int> a;
  f(i,0,n) a[i] = _A[i];
  for(auto i : a) C.add(i);
  vt<pr<int,int>> queries;
  f(j,0,q){
  	int i = _X[j], x = _V[j]; //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);
  
  ordered_set<int> os;
  f(i,0,n){
  	os.insert((a[i]<<int(LOG))+i);
  }
  
  IMPLICIT_TREAP treap;
  
  auto position = [&](int i) -> int {
  	int val = (a[i] << int(LOG)) + i;
  	return int(os.order_of_key(val));
  };
  
  auto add_os = [&](int i) -> void {
  	int val = (a[i] << int(LOG)) + i;
  	os.insert(val);
  };
  
  auto remove_os = [&](int i) -> void {
  	int val = (a[i] << int(LOG)) + i;
  	os.erase(os.find(val));
  };
  
  f(i,0,n){
  	int in = position(i);
  	treap.insert(in,i - in);
  }
  
  vt<int> ans;
  for(auto [i,x]:queries){
  	int in = position(i);
  	remove_os(i);
  	a[i] = x;
  	add_os(i);
  	int nxt = position(i);
  	//__f("in,nxt",in,nxt);
  	if(in < nxt){
  		treap.insert(nxt+1,i-nxt-1);
  		treap.del(in);
  		treap.range_update(in,nxt,1);
  	}else if(in > nxt){
  		treap.del(in);
  		treap.insert(nxt,i-nxt);
  		treap.range_update(nxt+1,in,-1);
  	}
  	ans.pb(treap.range_query(0,n-1));
  }

#undef int
	vt<int> out(q);
	f(i,0,q) out[i] = ans[i];
  return out;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40