Submission #199384

# Submission time Handle Problem Language Result Execution time Memory
199384 2020-01-31T23:01:31 Z mahmoudbadawy Bubble Sort 2 (JOI18_bubblesort2) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;


struct node
{
	pair<int,int> val;
	int prio,maxi,lazy,mv,co;
	node* pa;
	node* l; node* r;
	node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
	node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
};

int getco(node* n)
{
	if(!n) return 0;
	return n->co;
}

void update(node* &x)
{
	if(x)
	{
		x->mv+=x->lazy;
		x->maxi=x->mv;
		x->co=1;
		if(x->l)
		{
			x->l->maxi+=x->lazy; x->l->lazy+=x->lazy;
			x->maxi=max(x->maxi,x->l->maxi);
			x->co+=x->l->co;
		}
		if(x->r)
		{
			x->r->maxi+=x->lazy; x->r->lazy+=x->lazy;
			x->maxi=max(x->maxi,x->r->maxi);
			x->co+=x->r->co;
		}
		x->lazy=0;
	}
}

void split(node *root,node* &l,node* &r,pair<int,int> ind,node* lpa=0,node* rpa=0)
{
	if(root==0)
	{
		l=r=0; return;
	}
	if(ind<root->val)
	{
		r=root;
		split(root->l,l,r->l,ind,lpa,r);
		if(r) r->pa=rpa;
		update(r);
	}
	else
	{
		l=root;
		split(root->r,l->r,r,ind,l,rpa);
		if(l) l->pa=lpa;
		update(l);
	}
	update(root);
}

void merge(node* &root,node* l,node *r,node* pa=0)
{
	if(l==0)
	{
		root=r;
	}
	else if(r==0)
	{
		root=l;
	}
	else if(l->prio>r->prio)
	{
		root=l;
		merge(l->r,l->r,r,root);
	}
	else
	{
		root=r;
		merge(r->l,l,r->l,root);
	}
	if(root) root->pa=pa;
	update(root);
}

void insert(node* &root,node* cur,pair<int,int> val)
{
	node* l1; node* l2;
	split(root,l1,l2,val);
	merge(root,l1,cur); merge(root,root,l2);
}


const int N=1e5+5;

node* root;
int n,q;

void print(node * root,int dep=0){
	if(root){
		cout << string(dep,' ');
		printf("%d %d\n ", (root->val).first, root->co);
		print(root->l,dep+1);
		print(root->r,dep+1);
	}
}

void modify(int ox,int nx,int i)
{
	node *a,*x,*y,*b;
	// update the value
	split(root,a,x,{ox,i-1});
	split(x,y,b,{ox,i});
	y->val={nx,i};
	// update the numeber of moves
	if(nx>ox)
	{
		split(b,x,b,{nx,i});
		// a x y b
		y->mv=i/2-(getco(a)+getco(x));
		if(x) {x->lazy+=1; update(x);}
		merge(root,a,x);
		merge(root,root,y);
		merge(root,root,b);
	}
	else
	{
		merge(b,x,b);
		split(a,a,x,{nx,i});
		// a y x b
		y->mv=i/2-getco(a);
		if(x) {x->lazy-=1; update(x);}
		merge(root,a,y);
		merge(root,root,b);
	}
}


std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	n=A.size(),q=X.size();	
	vector<pair<int,int> > v;
	for(int i=0;i<A.size();i++)
		v.push_back({A[i],2*i});
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++)
	{
	    node* cur=new node(v[i],v[i].second/2-i);
		insert(root,cur,v[i]);
	}
	//print(root);
	vector<int> ans;
	for(int i=0;i<q;i++)
	{
	    if(A[X[i]]!=V[i])
		    modify(A[X[i]],V[i],2*X[i]);
		A[X[i]]=V[i];
		ans.push_back(root->maxi);
		//cout << (root->maxi) << endl;
		//print(root);
	}
	return ans;
}


#include <cstdio>
#include <cstdlib>
#include <vector>

int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();
	
	std::vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
	
	std::vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
	
	std::vector<int> res=countScans(A,X,V);
	
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
	return 0;
}

Compilation message

bubblesort2.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
bubblesort2.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
bubblesort2.cpp: In constructor 'node::node()':
bubblesort2.cpp:14:17: warning: 'node::r' will be initialized after [-Wreorder]
  node* l; node* r;
                 ^
bubblesort2.cpp:13:8: warning:   'node* node::pa' [-Wreorder]
  node* pa;
        ^~
bubblesort2.cpp:15:2: warning:   when initialized here [-Wreorder]
  node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
  ^~~~
bubblesort2.cpp:13:8: warning: 'node::pa' will be initialized after [-Wreorder]
  node* pa;
        ^~
bubblesort2.cpp:12:16: warning:   'int node::lazy' [-Wreorder]
  int prio,maxi,lazy,mv,co;
                ^~~~
bubblesort2.cpp:15:2: warning:   when initialized here [-Wreorder]
  node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
  ^~~~
bubblesort2.cpp:12:16: warning: 'node::lazy' will be initialized after [-Wreorder]
  int prio,maxi,lazy,mv,co;
                ^~~~
bubblesort2.cpp:12:11: warning:   'int node::maxi' [-Wreorder]
  int prio,maxi,lazy,mv,co;
           ^~~~
bubblesort2.cpp:15:2: warning:   when initialized here [-Wreorder]
  node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
  ^~~~
bubblesort2.cpp: In constructor 'node::node(std::pair<int, int>, int)':
bubblesort2.cpp:12:21: warning: 'node::mv' will be initialized after [-Wreorder]
  int prio,maxi,lazy,mv,co;
                     ^~
bubblesort2.cpp:12:6: warning:   'int node::prio' [-Wreorder]
  int prio,maxi,lazy,mv,co;
      ^~~~
bubblesort2.cpp:16:2: warning:   when initialized here [-Wreorder]
  node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
  ^~~~
bubblesort2.cpp:14:17: warning: 'node::r' will be initialized after [-Wreorder]
  node* l; node* r;
                 ^
bubblesort2.cpp:13:8: warning:   'node* node::pa' [-Wreorder]
  node* pa;
        ^~
bubblesort2.cpp:16:2: warning:   when initialized here [-Wreorder]
  node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
  ^~~~
bubblesort2.cpp:13:8: warning: 'node::pa' will be initialized after [-Wreorder]
  node* pa;
        ^~
bubblesort2.cpp:12:16: warning:   'int node::lazy' [-Wreorder]
  int prio,maxi,lazy,mv,co;
                ^~~~
bubblesort2.cpp:16:2: warning:   when initialized here [-Wreorder]
  node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
  ^~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:151:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++)
              ~^~~~~~~~~
/tmp/ccvJEnMO.o: In function `readInt()':
grader.cpp:(.text+0x0): multiple definition of `readInt()'
/tmp/ccRpNeW7.o:bubblesort2.cpp:(.text+0x5f0): first defined here
/tmp/ccvJEnMO.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccRpNeW7.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status