Submission #64847

#	Time	Username	Problem	Language	Result	Execution time	Memory
64847		TadijaSebez	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	7848 ms	144012 KiB

bubblesort2

#include "bubblesort2.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <ctime>
using namespace std;
#define pb push_back
#define mp make_pair
int max(int a, int b){ return a>b?a:b;}
const int N=500050;
const int M=2*N;
int ls[M],rs[M],tsz,root,val[M],Max[M],lzy[M],sz[M],y[M];
pair<int,int> id[M];
int MakeNode(pair<int,int> p, int v)
{
	tsz++;
	val[tsz]=Max[tsz]=v;
	id[tsz]=p;
	lzy[tsz]=0;
	sz[tsz]=1;
	y[tsz]=rand();
	return tsz;
}
void Push(int c)
{
	if(!c || !lzy[c]) return;
	if(ls[c]) Max[ls[c]]+=lzy[c],val[ls[c]]+=lzy[c],lzy[ls[c]]+=lzy[c];
	if(rs[c]) Max[rs[c]]+=lzy[c],val[rs[c]]+=lzy[c],lzy[rs[c]]+=lzy[c];
	lzy[c]=0;
}
void Pull(int c)
{
	if(!c) return;
	Push(c);
	Max[c]=val[c];
	sz[c]=sz[ls[c]]+sz[rs[c]]+1;
	if(ls[c]) Max[c]=max(Max[c],Max[ls[c]]);
	if(rs[c]) Max[c]=max(Max[c],Max[rs[c]]);
}
void Rotate1(int &c)
{
	int a=ls[c],b=rs[a];
	Push(c);Push(a);
	ls[c]=b;
	rs[a]=c;
	Pull(c);Pull(a);
	c=a;
}
void Rotate2(int &c)
{
	int a=rs[c],b=ls[a];
	Push(c);Push(a);
	rs[c]=b;
	ls[a]=c;
	Pull(c);Pull(a);
	c=a;
}
void Del(int &c, pair<int,int> p)
{
	if(!c) return;
	Push(c);
	if(id[c]==p)
	{
		if(!ls[c]) c=rs[c];
		else if(!rs[c]) c=ls[c];
		else if(y[ls[c]]>y[rs[c]]) Rotate1(c),Del(rs[c],p);
		else Rotate2(c),Del(ls[c],p);
		Pull(c);
		return;
	}
	if(id[c]<p) Del(rs[c],p);
	else Del(ls[c],p);
	Pull(c);
}
void Add(int &c, pair<int,int> p, int x)
{
	if(!c){ c=MakeNode(p,x);return;}
	Push(c);
	if(id[c]<p)
	{
		Add(rs[c],p,x);
		if(y[rs[c]]>y[c]) Rotate2(c);
	}
	else
	{
		Add(ls[c],p,x);
		if(y[ls[c]]>y[c]) Rotate1(c);
	}
	Pull(c);
}
void Inc(int &c, pair<int,int> p, int f)
{
	if(!c) return;
	Push(c);
	if(id[c]<p) Inc(rs[c],p,f);
	else
	{
		val[c]+=f;
		if(rs[c]) val[rs[c]]+=f,Max[rs[c]]+=f,lzy[rs[c]]+=f;
		Inc(ls[c],p,f);
	}
	Pull(c);
}
int Count(int c, pair<int,int> p)
{
	if(!c) return 0;
	//printf("(%i %i)\n",id[c].first,id[c].second);
	if(id[c]<p)
	{
		int ans=sz[ls[c]]+1;
		ans+=Count(rs[c],p);
		return ans;
	}
	else return Count(ls[c],p);
}
void Print(int c)
{
	if(!c) return;
	Print(ls[c]);
	printf("(%i %i) ",id[c].first,id[c].second);
	Print(rs[c]);
}
void Print(){ Print(root);printf("\n");}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
	srand(time(0));
	int n,i,q;
	for(i=1;i<=tsz;i++) ls[i]=rs[i]=0;
	root=tsz=0;
	n=a.size();
	q=x.size();
	vector<pair<int,int> > id;
	for(i=0;i<n;i++) id.pb(mp(a[i],i));
	sort(id.begin(),id.end());
	for(i=0;i<n;i++)
	{
		int val=id[i].second-i;
		//printf("%i\n",val);
		Add(root,id[i],val);
	}
	//Print();
	vector<int> ret;
	for(i=0;i<q;i++)
	{
		Del(root,mp(a[x[i]],x[i]));
		//Print();
		Inc(root,mp(a[x[i]],x[i]),1);
		//Print();
		//printf("->%i\n",Max[root]);
		Inc(root,mp(v[i],x[i]),-1);
		//Print();
		//printf("->%i\n",Max[root]);
		int j=Count(root,mp(v[i],x[i]));
		//Print();
		Add(root,mp(v[i],x[i]),x[i]-j);
		//Print();
		//printf("%i<- %i %i\n",x[i]-j,x[i],j);
		a[x[i]]=v[i];
		ret.pb(Max[root]);
	}
	return ret;
}
//----------------------//
/*
void Swap(int &a, int &b){ a^=b,b^=a,a^=b;}
int Count(vector<int> a)
{
	int sol=0;
	bool sw=1;
	while(sw)
	{
		sw=0;
		for(int i=0;i+1<a.size();i++) if(a[i]>a[i+1]) Swap(a[i],a[i+1]),sw=1;
		if(sw) sol++;
	}
	return sol;
}
vector<int> Brute(vector<int> a, vector<int> x, vector<int> v)
{
	vector<int> ret;
	for(int i=0;i<x.size();i++)
	{
		a[x[i]]=v[i];
		ret.pb(Count(a));
	}
	return ret;
}
void StressTest()
{
	srand(time(0));
	vector<int> a,x,v;
	int c=0;
	for(int h=0;h<10000;h++)
	{
		int n=rand()%10+1,i,q=rand()%5+1;
		a.resize(n);x.resize(q);v.resize(q);
		for(i=0;i<n;i++) a[i]=rand()%100;
		for(i=0;i<q;i++) x[i]=rand()%n,v[i]=rand()%100;
		vector<int> sol1=countScans(a,x,v);
		vector<int> sol2=Brute(a,x,v);
		if(sol1!=sol2)
		{
			printf("Test case %i:\n",h+1);
			printf("%i %i\n",n,q);
			for(i=0;i<n;i++) printf("%i ",a[i]);printf("\n");
			for(i=0;i<q;i++) printf("%i %i\n",x[i],v[i]);
			printf("My sol: ");
			for(i=0;i<sol1.size();i++) printf("%i ",sol1[i]);printf("\n");
			printf("Brute Force: ");
			for(i=0;i<sol2.size();i++) printf("%i ",sol2[i]);printf("\n");
		}
		else c++;
	}
	printf("%i of %i is correct!\n",c,10000);
}
int main()
{
	StressTest();return 0;
	int n,q,i;
	vector<int> a,x,v;
	scanf("%i %i",&n,&q);
	a.resize(n);x.resize(q);v.resize(q);
	for(i=0;i<n;i++) scanf("%i",&a[i]);
	for(i=0;i<q;i++) scanf("%i %i",&x[i],&v[i]);
	vector<int> sol=countScans(a,x,v);
	for(i=0;i<sol.size();i++) printf("%i\n",sol[i]);
	return 0;
}
*/
//----------------------//

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