Submission #364980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
364980	2021-02-10T16:56:12 Z	r57shell	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	656 ms	524292 KB

bubblesort2

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

using namespace std;

static int stupid(vector<int> A)
{
	int res = 0;
	int n = A.size();
	while (true)
	{
		bool was = false;
		for (int i = 1; i < n; ++i)
		{
			if (A[i-1] > A[i])
			{
				swap(A[i-1], A[i]);
				was = true;
			}
		}
		if (was)
			++res;
		else
			break;
	}
	return res;
}

static int get(vector<int> &f, int x)
{
	int res = 0;
	for (; x >= 0; x = (x&(x+1))-1)
		res += f[x];
	return res;
}

static void add(vector<int> &f, int x, int v)
{
	for (; x < f.size(); x |= (x+1))
		f[x] += v;
}

static int stupid1(vector<int> A)
{
	int n = A.size();
	int res = 0;
	for (int i = 1; i < n; ++i)
	{
		int c = 0;
		for (int j = 0; j < i; ++j)
			if (A[i] < A[j])
				++c;
		res = max(res, c);
	}
	return res;
}

static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
{
	int n = A.size();
	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		res = max(res, i - get(F, A[i]));
		add(F, A[i], 1);
	}
	for (int i = 0; i < n; ++i)
		add(F, A[i], -1);
	return res;
}

static int smart1(const vector<int> &A)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int j = 0; j < i; ++j)
				if (A[i] < A[j])
					++c;
			res = max(res, c);
		}
	}
	return res;
}

void merge(vector<int> &res, const vector<int> &a, const vector<int> &b)
{
	int i, j, k;
	res.resize(a.size()+b.size());
	k = 0;
	for (i = 0, j = 0; i < a.size() && j < b.size(); )
	{
		if (a[i] <= b[j])
			res[k++] = a[i++];
		else
			res[k++] = b[j++];
	}
	for (; i < a.size(); ++i, ++k)
		res[k] = a[i];
	for (; j < b.size(); ++j, ++k)
		res[k] = b[j];
}

static int smart2(const vector<int> &A, vector<vector<int>> &T)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	for (int i = 0; i < n; ++i)
		T[i+n].assign(1, A[i]);
	for (int i = n - 1; i > 0; --i)
		merge(T[i], T[i*2], T[i*2+1]);
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			int l = 0 + n;
			int r = i + n;
			while (l <= r)
			{
				if (l&1)
					c += T[l].size() - (lower_bound(T[l].begin(), T[l].end(), p + 1) - T[l].begin());
				if (!(r&1))
					c += T[r].size() - (lower_bound(T[r].begin(), T[r].end(), p + 1) - T[r].begin());
				l = (l+1)/2;
				r = (r-1)/2;
			}
			res = max(res, c);
		}
	}
	return res;
}

static int smart3(const vector<int> &A, vector<vector<int>> &T)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	for (int i = 0; i < n; ++i)
		T[i].clear();
	/*for (int i = 0; i < n; ++i)
		printf("%d ", A[i]);
	printf("\n");*/
	vector<int> v, v1;
	for (int i = 0; i < n; ++i)
	{
		//for (int x = i; x < n; x = (x|(x+1)))
		//	T[x].push_back(A[i]);
			//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
		v.assign(1, A[i]);
		v1.clear();
		int y = (i&(i+1))-1;
		for (int x = i - 1; x > y; x = (x&(x+1))-1)
		{
			merge(v1, v, T[x]);
			swap(v1, v);
		}
		T[i] = v;
	}
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int x = i; x >= 0; x = (x&(x+1))-1)
				c += T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin());
			res = max(res, c);
		}
	}
	return res;
}

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

void traverse(node *a)
{
	if (!a)
		return;
	traverse(a->left);
	printf("%d ", a->v);
	fflush(stdout);
	traverse(a->right);
}

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

node * merge(node *a, node *b)
{
	if (!a)
		return b;
	if (!b)
		return a;
	node *r = new node();
	//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]);
	if (a->h < b->h)
	{
		*r = *a;
		node *a_right = a->right;
		if (r->pv)
		{
			int delta = r->pv;
			if (a->left)
			{
				node *nl = new node();
				*nl = *a->left;
				nl->pv += delta;
				nl->mv += delta;
				nl->v1 += delta;
				r->left = nl;
			}
			if (a->right)
			{
				a_right = new node();
				*a_right = *a->right;
				a_right->pv += delta;
				a_right->mv += delta;
				a_right->v1 += delta;
			}
			r->pv = 0;
		}
		r->right = merge(a_right, b);
	}
	else
	{
		*r = *b;
		node *b_left = b->left;
		if (r->pv)
		{
			int delta = r->pv;
			if (b->right)
			{
				node *nr = new node();
				*nr = *b->right;
				nr->pv += delta;
				nr->mv += delta;
				nr->v1 += delta;
				r->right = nr;
			}
			if (b->left)
			{
				b_left = new node();
				*b_left = *b->left;
				b_left->pv += delta;
				b_left->mv += delta;
				b_left->v1 += delta;
			}
			r->pv = 0;
		}
		r->left = merge(a, b_left);
	}
	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*> split(node *a, int x)
{
	if (!a)
		return pair<node*,node*>((node*)0, (node*)0);
	pair<node*,node*> tmp;
	//vector<int> qwe = grab(a,0);
	//pair<node*,node*> ans;
	if (x <= a->v)
	{
		node * a_left = a->left;
		if (a->pv && a_left)
		{
			int pv = a->pv;
			a_left = new node();
			*a_left = *a->left;
			a_left->pv += pv;
			a_left->mv += pv;
			a_left->v1 += pv;
		}
		tmp = split(a_left,x);
		node * z = new node();
		*z = *a;
		z->left = NULL;
		if (a->left)
			z->sz -= a->left->sz;
		z->mv = z->v1;
		if (z->right)
			z->mv = max(z->mv, z->right->mv + z->pv);
		return pair<node*,node*>(tmp.first, merge(tmp.second,z));
	}
	else
	{
		node *a_right = a->right;
		if (a->pv && a_right)
		{
			int pv = a->pv;
			a_right = new node();
			*a_right = *a->right;
			a_right->pv += pv;
			a_right->mv += pv;
			a_right->v1 += pv;
		}
		tmp = split(a_right,x);
		node * z = new node();
		*z = *a;
		z->right = NULL;
		if (a->right)
			z->sz -= a->right->sz;
		z->mv = z->v1;
		if (z->left)
			z->mv = max(z->mv, z->left->mv + z->pv);
		return pair<node*,node*>(merge(z, tmp.first), tmp.second);
	}
	/*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 * removefirst(node *a)
{
	//string z = tostr(a);
	node *r = NULL;
	//string ll = tostr(a->left);
	//string rr = tostr(a->right);
	if (a->left)
	{
		node *q = new node();
		*q = *a;
		node *a_left = a->left;
		if (a->pv)
		{
			a_left = new node();
			*a_left = *(a->left);
			a_left->pv += a->pv;
			a_left->v1 += a->pv;
			a_left->mv += a->pv;
		}
		q->left = NULL;
		q->sz -= a->left->sz;
		q->mv = q->v1;
		if (q->right)
			q->mv = max(q->mv, q->pv + q->right->mv);
		r = merge(removefirst(a_left), q);
	}
	else
	{
		node *a_right = a->right;
		if (a_right && a->pv)
		{
			a_right = new node();
			*a_right = *(a->right);
			a_right->pv += a->pv;
			a_right->v1 += a->pv;
			a_right->mv += a->pv;
		}
		r = 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);
}

static int smart4(const vector<int> &A)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	vector<node*> D(2*n);
	{
		vector<vector<int>> T(2*n);
		/*for (int i = 0; i < n; ++i)
			printf("%d ", A[i]);
		printf("\n");*/
		vector<int> v, v1;
		for (int i = 0; i < n; ++i)
		{
			//for (int x = i; x < n; x = (x|(x+1)))
			//	T[x].push_back(A[i]);
				//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
			v.assign(1, A[i]);
			v1.clear();
			int y = (i&(i+1))-1;
			for (int x = i - 1; x > y; x = (x&(x+1))-1)
			{
				merge(v1, v, T[x]);
				swap(v1, v);
			}
			T[i] = v;
			D[i] = NULL;
			for (int j = 0; j < v.size(); ++j)
			{
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = v[j];
				nd->left = NULL;
				nd->right = NULL;
				nd->sz = 1;
				D[i] = merge(D[i], nd);
			}
		}
	}
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int x = i; x >= 0; x = (x&(x+1))-1)
			{
				//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
				c += D[x]->sz - getsz(D[x], p+1);
			}
			res = max(res, c);
		}
	}
	return res;
}

static int smart5(const vector<int> &A, vector<node*> &D)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	if (D.size() == 0)
	{
		D.resize(2*n);
		vector<vector<int>> T(2*n);
		/*for (int i = 0; i < n; ++i)
			printf("%d ", A[i]);
		printf("\n");*/
		vector<int> v, v1;
		for (int i = 0; i < n; ++i)
		{
			//for (int x = i; x < n; x = (x|(x+1)))
			//	T[x].push_back(A[i]);
				//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
			v.assign(1, A[i]);
			v1.clear();
			int y = (i&(i+1))-1;
			for (int x = i - 1; x > y; x = (x&(x+1))-1)
			{
				merge(v1, v, T[x]);
				swap(v1, v);
			}
			T[i] = v;
			D[i] = NULL;
			for (int j = 0; j < v.size(); ++j)
			{
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = v[j];
				nd->left = NULL;
				nd->right = NULL;
				nd->sz = 1;
				D[i] = merge(D[i], nd);
			}
		}
	}
	for (int i = n - 1; i > 0; --i)
	{
		if (A[i] < p)
		{
			p = A[i];
			int c = 0;
			for (int x = i; x >= 0; x = (x&(x+1))-1)
			{
				//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
				c += D[x]->sz - getsz(D[x], p+1);
			}
			res = max(res, c);
		}
	}
	return res;
}

vector<int> countScans1(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();
	int N = A.size();
	vector<int> answer(Q);
	vector<node*> D;
	//vector<vector<int>> T(N);
	for (int j = 0; j < Q; ++j)
	{
		//printf("j %d\n", j);
		if (j != 0)
		{
			//for (int x = 0; x < N; ++x)
			//	printf("%d ", A[x]);
			//printf("\n");
			//printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);
			for (int x = X[j]; x < N; x = (x|(x+1)))
			{
				//printf("D[%d] = %d (sz = %d)\n", x, D[x], D[x]->sz);
				//traverse(D[x]);
				//printf("\n");
				pair<node*,node*> tmp = split(D[x], A[X[j]]);
				//traverse(tmp.first);
				//printf(", ");
				//traverse(tmp.second);
				//printf("\n");
				tmp.second = removefirst(tmp.second);
				//traverse(tmp.second);
				//printf("\n");
				node * q = merge(tmp.first, tmp.second);
				//printf("=");
				//traverse(q);
				//printf("\n");
				tmp = split(q,V[j]);
				node * nn = new node();
				nn->h = rand()*32000+rand();
				nn->left = 0;
				nn->right = 0;
				nn->sz = 1;
				nn->v = V[j];
				//printf("D[%d] = ", x);
				D[x] = merge(merge(tmp.first, nn), tmp.second);
				//traverse(D[x]);
				//printf("\n");
			}
		}
		A[X[j]] = V[j];
		answer[j] = smart5(A, D);
	}
	return answer;
}

node* getleft(node *a)
{
	if (a->left)
		return getleft(a->left);
	return a;
}

vector<node*> DS;
vector<vector<pair<int,int>>> DP;

void apply_push(int x)
{
	vector<pair<int,int>> &v = DP[x];
	for (int i = 0; i < v.size(); ++i)
	{
		int a = v[i].first;
		int delta = v[i].second;
		if (x*2+1 < DP.size())
		{
			DP[x*2].push_back(v[i]);
			DP[x*2+1].push_back(v[i]);
		}
		//printf("before split DS[%d] \"%s\" (%d, %d)\n", x, tostr(DS[x]).c_str(), a, delta);
		pair<node*,node*> q = split(DS[x], a);
		//printf("after split \"%s\" (%d, %d) \"%s\"\n", tostr(q.first).c_str(), a, delta, tostr(q.second).c_str());
		if (q.first)
		{
			node *nn = new node();
			*nn = *(q.first);
			nn->pv += delta;
			nn->mv += delta;
			nn->v1 += delta;
			DS[x] = merge(nn, q.second);
		}
		else
			DS[x] = q.second;
		//printf("result \"%s\"\n", tostr(DS[x]).c_str());
	}
	v.clear();
}

void merge_seq(int x)
{
	apply_push(x*2+1);
	node *right = DS[x*2+1];
	int cut;
	if (right)
		cut = getleft(right)->v;
	else
		cut = int(2e9);
	apply_push(x*2);
	node *left = DS[x*2];
	pair<node*, node*> tmp = split(left, cut);
	DS[x] = merge(tmp.first, right);
}

void add_ab(int x, int a, int v)
{
	DP[x].push_back(pair<int,int>(a,v));
}

void dsupdate(int x, int pos, int was, int now, int inv, int L, int R)
{
	//printf("%d %d %d\n", x, L, R);
	if (R < pos)
		return;
	if (pos < L)
	{
		add_ab(x, was, -1);
		add_ab(x, now, 1);
		return;
	}
	if (L == R)
	{
		DP[x].clear();
		node * nn = new node();
		*nn = *(DS[x]);
		nn->v = now;
		nn->v1 = inv;
		nn->pv = 0;
		nn->mv = inv;
		DS[x] = nn;
		return;
	}
	int z = DP[x].size();
	for (int i = 0; i < z; ++i)
	{
		DP[2*x].push_back(DP[x][i]);
		DP[2*x+1].push_back(DP[x][i]);
	}
	DP[x].clear();
	int m = (L + R)/2;
	dsupdate(2 * x, pos, was, now, inv, L, m);
	dsupdate(2 * x + 1, pos, was, now, inv, m + 1, R);
	merge_seq(x);
	//printf("DS[%d]=%s\n",x,tostr(DS[x]).c_str());
}


vector<int> countScans2(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();
	int N = A.size();
	vector<int> answer(Q);
	vector<node*> D(N);
	int TSTART = 2;
	while (TSTART / 2 < N)
		TSTART *= 2;
	DS.resize(2*TSTART);
	DP.resize(2*TSTART);
	for (int j = 0; j < Q; ++j)
	{
		//printf("j %d\n", j);
		if (j == 0)
		{
			vector<vector<int>> T(2*N);
			A[X[j]] = V[j];
			/*for (int i = 0; i < N; ++i)
				printf("%d ", A[i]);
			printf("\n");*/
			vector<int> v, v1;
			for (int i = 0; i < N; ++i)
			{
				//for (int x = i; x < n; x = (x|(x+1)))
				//	T[x].push_back(A[i]);
					//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
				v.assign(1, A[i]);
				v1.clear();
				int y = (i&(i+1))-1;
				for (int x = i - 1; x > y; x = (x&(x+1))-1)
				{
					merge(v1, v, T[x]);
					swap(v1, v);
				}
				T[i] = v;
				D[i] = NULL;
				for (int j = 0; j < v.size(); ++j)
				{
					node *nd = new node();
					nd->h = rand()*32000+rand();
					nd->v = v[j];
					nd->left = NULL;
					nd->right = NULL;
					nd->sz = 1;
					D[i] = merge(D[i], nd);
				}
			}
			for (int i = 0; i < N; ++i)
			{
				int p = A[i];
				int c = 0;
				for (int x = i; x >= 0; x = (x&(x+1))-1)
				{
					//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
					c += D[x]->sz - getsz(D[x], p+1);
				}
				node *nd = new node();
				nd->h = rand()*32000+rand();
				nd->v = A[i];
				nd->v1 = c;
				nd->pv = 0;
				nd->mv = c;
				nd->sz = 1;
				DS[i+TSTART] = nd;
			}
			for (int i = TSTART-1; i > 0; --i)
			{
				//printf("merge_seq(%d) =", i);
				merge_seq(i);
				//printf("%s\n", tostr(DS[i]).c_str());
			}
		}
		else
		{
			/*for (int x = 0; x < N; ++x)
				printf("%d ", A[x]);
			printf("\n");
			printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);*/
			int awas = A[X[j]];
			for (int x = X[j]; x < N; x = (x|(x+1)))
			{
				//printf("D[%d] = %d (sz = %d)\n", x, D[x], D[x]->sz);
				//traverse(D[x]);
				//printf("\n");
				pair<node*,node*> tmp = split(D[x], awas);
				//traverse(tmp.first);
				//printf(", ");
				//traverse(tmp.second);
				//printf("\n");
				tmp.second = removefirst(tmp.second);
				//traverse(tmp.second);
				//printf("\n");
				node * q = merge(tmp.first, tmp.second);
				//printf("=");
				//traverse(q);
				//printf("\n");
				tmp = split(q,V[j]);
				node * nn = new node();
				nn->h = rand()*32000+rand();
				nn->left = 0;
				nn->right = 0;
				nn->sz = 1;
				nn->v = V[j];
				//printf("D[%d] = ", x);
				D[x] = merge(merge(tmp.first, nn), tmp.second);
				//traverse(D[x]);
				//printf("\n");
			}
			{
				int p = V[j];
				int c = 0;
				for (int x = X[j]; x >= 0; x = (x&(x+1))-1)
				{
					//printf("yo %d %s\n", x, tostr(D[x]).c_str());
					//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
					c += D[x]->sz - getsz(D[x], p+1);
				}
				//printf("dsupdate inv = %d\n", c);
				dsupdate(1, X[j], awas, V[j], c, 0, TSTART-1);
			}
			/*{
				int x = TSTART + X[j];
				node * nn = new node();
				*nn = *(DS[x]);
				nn->v = V[j];
				nn->mv = v;
				while( x > 1 )
				{
					x /= 2;
					merge_seq(x);
				}
			}*/
		}
		A[X[j]] = V[j];
		apply_push(1);
		//printf("ans=%d\n", DS[1]->mv);
		answer[j] = DS[1]->mv;//smart5(A, D);
	}
	return answer;
}

node* add_bigger(node* n, int x, int delta)
{
	pair<node*,node*> s = split(n, x);
	//printf("add_bigger %d %d [%s] [%s]\n", x, delta, tostr(s.first).c_str(), tostr(s.second).c_str());
	if (s.second)
	{
		node *nr = new node();
		*nr = *(s.second);
		nr->pv += delta;
		nr->v1 += delta;
		nr->mv += delta;
		s.second = nr;
	}
	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;
}


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;
	if (pair<int, int>(x, idx) <= pair<int,int>(a->v, a->idx))//(x < a->v || (x == a->v && idx <= a->idx))
	{
		node * a_left = a->left;
		if (a->pv && a_left)
		{
			int pv = a->pv;
			a_left = new node();
			*a_left = *a->left;
			a_left->pv += pv;
			a_left->mv += pv;
			a_left->v1 += pv;
		}
		tmp = split_vidx(a_left,x,idx);
		node * z = new node();
		*z = *a;
		z->left = NULL;
		if (a->left)
			z->sz -= a->left->sz;
		z->mv = z->v1;
		if (z->right)
			z->mv = max(z->mv, z->right->mv + z->pv);
		return pair<node*,node*>(tmp.first, merge(tmp.second,z));
	}
	else
	{
		node *a_right = a->right;
		if (a->pv && a_right)
		{
			int pv = a->pv;
			a_right = new node();
			*a_right = *a->right;
			a_right->pv += pv;
			a_right->mv += pv;
			a_right->v1 += pv;
		}
		tmp = split_vidx(a_right,x,idx);
		node * z = new node();
		*z = *a;
		z->right = NULL;
		if (a->right)
			z->sz -= a->right->sz;
		z->mv = z->v1;
		if (z->left)
			z->mv = max(z->mv, z->left->mv + z->pv);
		return pair<node*,node*>(merge(z, tmp.first), tmp.second);
	}
	/*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;*/
}

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;
				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]);
			root = merge(s.first, removefirst(s.second));
			//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 = new node();
			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;
			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

bubblesort2.cpp: In function 'void add(std::vector<int>&, int, int)':
bubblesort2.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (; x < f.size(); x |= (x+1))
      |         ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void merge(std::vector<int>&, const std::vector<int>&, const std::vector<int>&)':
bubblesort2.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (i = 0, j = 0; i < a.size() && j < b.size(); )
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:100:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (i = 0, j = 0; i < a.size() && j < b.size(); )
      |                                     ~~^~~~~~~~~~
bubblesort2.cpp:107:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (; i < a.size(); ++i, ++k)
      |         ~~^~~~~~~~~~
bubblesort2.cpp:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for (; j < b.size(); ++j, ++k)
      |         ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> grab(node*, int)':
bubblesort2.cpp:226:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |  for (int i = 0; i < rb.size(); ++i)
      |                  ~~^~~~~~~~~~~
bubblesort2.cpp: In function 'int smart4(const std::vector<int>&)':
bubblesort2.cpp:476:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  476 |    for (int j = 0; j < v.size(); ++j)
      |                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'int smart5(const std::vector<int>&, std::vector<node*>&)':
bubblesort2.cpp:533:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  533 |    for (int j = 0; j < v.size(); ++j)
      |                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void apply_push(int)':
bubblesort2.cpp:627:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  627 |  for (int i = 0; i < v.size(); ++i)
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:631:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  631 |   if (x*2+1 < DP.size())
      |       ~~~~~~^~~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans2(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:750:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  750 |     for (int j = 0; j < v.size(); ++j)
      |                     ~~^~~~~~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:449:12: warning: 'int smart4(const std::vector<int>&)' defined but not used [-Wunused-function]
  449 | static int smart4(const vector<int> &A)
      |            ^~~~~~
bubblesort2.cpp:145:12: warning: 'int smart3(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
  145 | static int smart3(const vector<int> &A, vector<vector<int>> &T)
      |            ^~~~~~
bubblesort2.cpp:113:12: warning: 'int smart2(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
  113 | static int smart2(const vector<int> &A, vector<vector<int>> &T)
      |            ^~~~~~
bubblesort2.cpp:75:12: warning: 'int smart1(const std::vector<int>&)' defined but not used [-Wunused-function]
   75 | static int smart1(const vector<int> &A)
      |            ^~~~~~
bubblesort2.cpp:61:12: warning: 'int smart(const std::vector<int>&, std::vector<int>&, const std::vector<int>&)' defined but not used [-Wunused-function]
   61 | static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
      |            ^~~~~
bubblesort2.cpp:46:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
   46 | static int stupid1(vector<int> A)
      |            ^~~~~~~
bubblesort2.cpp:9:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
    9 | static int stupid(vector<int> A)
      |            ^~~~~~

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7532 KB	Output is correct
2	Correct	16 ms	13420 KB	Output is correct
3	Correct	42 ms	34176 KB	Output is correct
4	Correct	43 ms	34540 KB	Output is correct
5	Correct	42 ms	34156 KB	Output is correct
6	Correct	38 ms	29804 KB	Output is correct
7	Correct	39 ms	31980 KB	Output is correct
8	Correct	39 ms	31212 KB	Output is correct
9	Correct	42 ms	33644 KB	Output is correct
10	Correct	38 ms	30700 KB	Output is correct
11	Correct	40 ms	32364 KB	Output is correct
12	Correct	40 ms	32492 KB	Output is correct
13	Correct	41 ms	33772 KB	Output is correct
14	Correct	37 ms	30572 KB	Output is correct
15	Correct	39 ms	31212 KB	Output is correct
16	Correct	39 ms	32492 KB	Output is correct
17	Correct	38 ms	29420 KB	Output is correct
18	Correct	36 ms	29036 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7532 KB	Output is correct
2	Correct	16 ms	13420 KB	Output is correct
3	Correct	42 ms	34176 KB	Output is correct
4	Correct	43 ms	34540 KB	Output is correct
5	Correct	42 ms	34156 KB	Output is correct
6	Correct	38 ms	29804 KB	Output is correct
7	Correct	39 ms	31980 KB	Output is correct
8	Correct	39 ms	31212 KB	Output is correct
9	Correct	42 ms	33644 KB	Output is correct
10	Correct	38 ms	30700 KB	Output is correct
11	Correct	40 ms	32364 KB	Output is correct
12	Correct	40 ms	32492 KB	Output is correct
13	Correct	41 ms	33772 KB	Output is correct
14	Correct	37 ms	30572 KB	Output is correct
15	Correct	39 ms	31212 KB	Output is correct
16	Correct	39 ms	32492 KB	Output is correct
17	Correct	38 ms	29420 KB	Output is correct
18	Correct	36 ms	29036 KB	Output is correct
19	Correct	188 ms	143980 KB	Output is correct
20	Correct	206 ms	165612 KB	Output is correct
21	Correct	222 ms	180588 KB	Output is correct
22	Correct	204 ms	162540 KB	Output is correct
23	Correct	191 ms	154732 KB	Output is correct
24	Correct	204 ms	165740 KB	Output is correct
25	Correct	188 ms	155116 KB	Output is correct
26	Correct	199 ms	153708 KB	Output is correct
27	Correct	176 ms	142444 KB	Output is correct
28	Correct	177 ms	145644 KB	Output is correct

Subtask #3

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	185 ms	142828 KB	Output is correct
2	Runtime error	656 ms	524292 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7532 KB	Output is correct
2	Correct	16 ms	13420 KB	Output is correct
3	Correct	42 ms	34176 KB	Output is correct
4	Correct	43 ms	34540 KB	Output is correct
5	Correct	42 ms	34156 KB	Output is correct
6	Correct	38 ms	29804 KB	Output is correct
7	Correct	39 ms	31980 KB	Output is correct
8	Correct	39 ms	31212 KB	Output is correct
9	Correct	42 ms	33644 KB	Output is correct
10	Correct	38 ms	30700 KB	Output is correct
11	Correct	40 ms	32364 KB	Output is correct
12	Correct	40 ms	32492 KB	Output is correct
13	Correct	41 ms	33772 KB	Output is correct
14	Correct	37 ms	30572 KB	Output is correct
15	Correct	39 ms	31212 KB	Output is correct
16	Correct	39 ms	32492 KB	Output is correct
17	Correct	38 ms	29420 KB	Output is correct
18	Correct	36 ms	29036 KB	Output is correct
19	Correct	188 ms	143980 KB	Output is correct
20	Correct	206 ms	165612 KB	Output is correct
21	Correct	222 ms	180588 KB	Output is correct
22	Correct	204 ms	162540 KB	Output is correct
23	Correct	191 ms	154732 KB	Output is correct
24	Correct	204 ms	165740 KB	Output is correct
25	Correct	188 ms	155116 KB	Output is correct
26	Correct	199 ms	153708 KB	Output is correct
27	Correct	176 ms	142444 KB	Output is correct
28	Correct	177 ms	145644 KB	Output is correct
29	Correct	185 ms	142828 KB	Output is correct
30	Runtime error	656 ms	524292 KB	Execution killed with signal 9
31	Halted	0 ms	0 KB	-