Submission #365002

#	Time	Username	Problem	Language	Result	Execution time	Memory
365002		r57shell	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	5679 ms	60528 KiB

bubblesort2

#include "bubblesort2.h"
#include <cstdio>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

struct node
{
	node *left;
	node *right;
	int h;
	int v;
	int idx;
	int v1;
	int sz;
	int pv;
	int mv;
};

string tostr(node *a)
{
	if (!a)
		return string();
	string r = tostr(a->left);
	char tmp[20];
	sprintf(tmp," (%d, %d, %d, %d, %d)", a->v, a->v1, a->mv, a->pv, a->idx);
	r += tmp;
	return r + tostr(a->right);
}

vector<int> grab(node *a, int pv)
{
	if (!a)
		return vector<int>();
	vector<int> r = grab(a->left, pv+a->pv);
	r.push_back(pv+a->v1);
	vector<int> rb = grab(a->right, pv+a->pv);
	for (int i = 0; i < rb.size(); ++i)
		r.push_back(rb[i]);
	return r;
}

void push(node *a)
{
	int pv = a->pv;
	if (pv)
	{
		a->pv = 0;
		if (a->left)
		{
			a->left->pv += pv;
			a->left->v1 += pv;
			a->left->mv += pv;
		}
		if (a->right)
		{
			a->right->pv += pv;
			a->right->v1 += pv;
			a->right->mv += pv;
		}
	}
}

node * merge(node *a, node *b)
{
	if (!a)
		return b;
	if (!b)
		return a;
	push(a);
	push(b);
	//vector<int> qwe = grab(a,0);
	//vector<int> qwe1 = grab(b,0);
	//for (int i = 0; i < qwe1.size(); ++i)
	//	qwe.push_back(qwe1[i]);
	node *r;
	if (a->h < b->h)
	{
		a->right = merge(a->right, b);
		r = a;
	}
	else
	{
		b->left = merge(a, b->left);
		r = b;
	}
	r->sz = 1;
	r->mv = r->v1;
	if (r->left)
	{
		r->sz += r->left->sz;
		r->mv = max(r->mv, r->left->mv);
	}
	if (r->right)
	{
		r->sz += r->right->sz;
		r->mv = max(r->mv, r->right->mv);
	}
	/*vector<int> qwe2 = grab(r,0);
	int mmm = int(-1e9);
	for (int i = 0; i < qwe.size(); ++i)
		mmm = max(mmm, qwe[i]);
	if (qwe != qwe2 || r->mv != mmm)
	{
		printf("======= wrong ==== %d %d\n", r->mv, mmm);
		for (int i = 0; i < qwe.size(); ++i)
			printf("%d ", qwe[i]);
		printf("\n");
		for (int i = 0; i < qwe2.size(); ++i)
			printf("%d ", qwe2[i]);
		printf("\n [%s] [%s]\n", tostr(a).c_str(), tostr(b).c_str());
	}*/
	return r;
}

pair<node*,node*> removefirst(node *a)
{
	//string z = tostr(a);
	pair<node*,node*> r;
	//string ll = tostr(a->left);
	//string rr = tostr(a->right);
	push(a);
	if (a->left)
	{
		node *a_left = a->left;
		a->left = NULL;
		a->sz -= a_left->sz;
		a->mv = a->v1;
		if (a->right)
			a->mv = max(a->v1, a->pv + a->right->mv);
		r = removefirst(a_left);
		r.first = merge(r.first, a);
	}
	else
	{
		node *a_right = a->right;
		if (a_right)
		{
			a->sz -= a_right->sz;
			a->right = NULL;
			a->mv = a->v1;
		}
		r.second = a;
		r.first = a_right;
	}
	//printf("remove first (%s) (%s) (%s) = %s\n", z.c_str(), ll.c_str(), rr.c_str(), tostr(r).c_str());
	return r;
}

int getsz(node *a, int x)
{
	if (!a)
		return 0;
	if (a->v < x)
		return (a->left ? a->left->sz : 0) + 1 + getsz(a->right, x);
	return getsz(a->left, x);
}

pair<node*,node*> split_vidx(node *a, int x, int idx)
{
	if (!a)
		return pair<node*,node*>((node*)0, (node*)0);
	pair<node*,node*> tmp;
	//vector<int> qwe = grab(a,0);
	//pair<node*,node*> ans;
	push(a);
	if (x < a->v || (x == a->v && idx <= a->idx))
	{
		if (a->left)
		{
			a->sz -= a->left->sz;
			tmp = split_vidx(a->left, x, idx);
			a->left = NULL;
			a->mv = a->v1;
			if (a->right)
				a->mv = max(a->mv, a->right->mv + a->pv);
			return pair<node*,node*>(tmp.first, merge(tmp.second,a));
		}
		else
			return pair<node*,node*>((node*)NULL,a);
	}
	else
	{
		if (a->right)
		{
			a->sz -= a->right->sz;
			tmp = split_vidx(a->right,x,idx);
			a->right = NULL;
			a->mv = a->v1;
			if (a->left)
				a->mv = max(a->mv, a->left->mv + a->pv);
			return pair<node*,node*>(merge(a, tmp.first), tmp.second);
		}
		else
			return pair<node*,node*>(a, (node*)NULL);
	}
	/*vector<int> qwe1 = grab(ans.first,0);
	vector<int> qwe2 = grab(ans.second,0);
	for (int i = 0; i < qwe2.size(); ++i)
		qwe1.push_back(qwe2[i]);
	if (qwe1 != qwe)
	{
		printf("======= wrong split ====\n");
		for (int i = 0; i < qwe.size(); ++i)
			printf("%d ", qwe[i]);
		printf("\n");
		for (int i = 0; i < qwe1.size(); ++i)
			printf("%d ", qwe1[i]);
		printf("\n [%s] %d\n", tostr(a).c_str(), x);
	}
	return ans;*/
}

node* add_bigger(node* n, int x, int delta)
{
	pair<node*,node*> s = split_vidx(n, x, 0);
	//printf("add_bigger %d %d [%s] [%s]\n", x, delta, tostr(s.first).c_str(), tostr(s.second).c_str());
	if (s.second)
	{
		s.second->pv += delta;
		s.second->v1 += delta;
		s.second->mv += delta;
	}
	node *r = merge(s.first, s.second);
	/*printf("%s\n", tostr(r).c_str());
	vector<int> aa = grab(r, 0);
	printf("[");
	for (int i = 0; i < aa.size(); ++i)
		printf("%d ", aa[i]);
	printf("]\n");*/
	return r;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();
	int N = A.size();
	vector<int> answer(Q);
	node* root = NULL;
	for (int j = 0; j < Q; ++j)
	{
		//printf("j %d\n", j);
		if (j == 0)
		{
			A[X[j]] = V[j];
			/*for (int i = 0; i < N; ++i)
				printf("%d ", A[i]);
			printf("\n");*/
			vector<int> B = A;
			sort(B.begin(), B.end());
			for (int i = 0; i < N; ++i)
			{
				int c = upper_bound(B.begin(), B.end(), A[i]) - B.begin();
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = A[i];
				nd->idx = i;
				nd->v1 = i + 1 - c;
				nd->pv = 0;
				nd->mv = nd->v1;
				nd->sz = 1;
				nd->left = NULL;
				nd->right = NULL;
				pair<node*,node*> s = split_vidx(root, A[i], i);
				//printf("split_vidx [%s] [%s]\n", tostr(s.first).c_str(), tostr(s.second).c_str());
				root = merge(merge(s.first, nd),s.second);
				//printf("init %d %s\n", i, tostr(root).c_str());
			}
		}
		else
		{
			/*for (int i = 0; i < N; ++i)
				printf("%d ", A[i]);
			printf("\n");
			printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);*/
			int awas = A[X[j]];
			pair<node*,node*> s = split_vidx(root, awas, X[j]);
			pair<node*,node*> rf = removefirst(s.second);
			root = merge(s.first, rf.first);
			//printf("after delete %s\n", tostr(root).c_str());
			root = add_bigger(root, awas,1);
			root = add_bigger(root, V[j],-1);
			//printf("after modification %s\n", tostr(root).c_str());
			int c = getsz(root, V[j]+1);
			//printf("sz = %d\n", c);
			node *nd = rf.second;
			nd->h = rand()*32000+rand();
			nd->v = V[j];
			nd->idx = X[j];
			nd->v1 = X[j] + 1 - c - 1;
			nd->pv = 0;
			nd->mv = nd->v1;
			nd->sz = 1;
			nd->left = NULL;
			nd->right = NULL;
			pair<node*,node*> s1 = split_vidx(root, V[j], X[j]);
			root = merge(merge(s1.first, nd),s1.second);
		}
		A[X[j]] = V[j];
		/*{
			vector<int> B = A;
			sort(B.begin(), B.end());
			vector<pair<pair<int,int>,int>> tmp2;
			for (int z = 0; z < N; ++z)
			{
				int c = upper_bound(B.begin(), B.end(), A[z]) - B.begin();
				tmp2.push_back(pair<pair<int,int>,int>(pair<int,int>(A[z],z),z+1-c));
			}
			sort(tmp2.begin(), tmp2.end());
			vector<int> tmp;
			for (int z = 0; z < N; ++z)
			{
				tmp.push_back(tmp2[z].second);
				printf("(%d %d %d)", tmp2[z].first.first, tmp2[z].first.second, tmp2[z].second);
			}
			printf("\n");
			vector<int> tmp1 = grab(root, 0);
			if (tmp1 != tmp)
			
				printf("====== wrong ====\n");
			{	for (int z = 0; z < tmp.size(); ++z)
					printf("%d ", tmp[z]);
				printf("\n");
				for (int z = 0; z < tmp1.size(); ++z)
					printf("%d ", tmp1[z]);
				printf("\n");
			}
		}
		printf("now %s ans = %d\n", tostr(root).c_str(), root->mv);*/
		answer[j] = root->mv;
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> grab(node*, int)':
bubblesort2.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < rb.size(); ++i)
      |                  ~~^~~~~~~~~~~

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