Submission #64844

#	Time	Username	Problem	Language	Result	Execution time	Memory
64844		TadijaSebez	Bubble Sort 2 (JOI18_bubblesort2)	C++11	0 / 100	23 ms	2160 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;
	if(id[c]<p)
	{
		int ans=sz[ls[c]]+1;
		ans+=Count(rs[c],p);
		return ans;
	}
	else return Count(rs[c],p);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
	srand(time(0));
	int n,i,q;
	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);
	}
	vector<int> ret;
	for(i=0;i<q;i++)
	{
		Del(root,mp(a[x[i]],x[i]));
		Inc(root,mp(a[x[i]],x[i]),1);
		Inc(root,mp(v[i],x[i]),-1);
		int j=Count(root,mp(v[i],x[i]));
		Add(root,mp(v[i],x[i]),x[i]-j);
		a[x[i]]=v[i];
		ret.pb(Max[root]);
	}
	return ret;
}
//----------------------//
/*
int main()
{
	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: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40