oj.uz

Submission #364647

# Submission time Handle Problem Language Result Execution time Memory
364647 2021-02-09T16:23:30 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 524288 KB 
#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 sz;
};

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", a->v);
	r += tmp;
	return r + tostr(a->right);
}

node * merge(node *a, node *b)
{
	if (!a)
		return b;
	if (!b)
		return a;
	node *r = new node();
	if (a->h < b->h)
	{
		*r = *a;
		r->right = merge(a->right, b);
	}
	else
	{
		*r = *b;
		r->left = merge(a, b->left);
	}
	r->sz = 1;
	if (r->left)
		r->sz += r->left->sz;
	if (r->right)
		r->sz += r->right->sz;
	return r;
}

pair<node*,node*> split(node *a, int x)
{
	if (!a)
		return pair<node*,node*>((node*)0, (node*)0);
	pair<node*,node*> tmp;
	if (x <= a->v)
	{
		tmp = split(a->left,x);
		node * z = new node();
		*z = *a;
		z->left = NULL;
		if (a->left)
			z->sz -= a->left->sz;
		return pair<node*,node*>(tmp.first, merge(tmp.second,z));
	}
	else
	{
		tmp = split(a->right,x);
		node * z = new node();
		*z = *a;
		z->right = NULL;
		if (a->right)
			z->sz -= a->right->sz;
		return pair<node*,node*>(merge(z, tmp.first), tmp.second);
	}
}

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;
		q->left = NULL;
		q->sz -= a->left->sz;
		r = merge(removefirst(a->left), q);
	}
	else
		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> countScans(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;
}

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 'int smart4(const std::vector<int>&)':
bubblesort2.cpp:323:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  323 |    for (int j = 0; j < v.size(); ++j)
      |                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'int smart5(const std::vector<int>&, std::vector<node*>&)':
bubblesort2.cpp:380:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  380 |    for (int j = 0; j < v.size(); ++j)
      |                    ~~^~~~~~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:296:12: warning: 'int smart4(const std::vector<int>&)' defined but not used [-Wunused-function]
  296 | 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 10 ms 6380 KB Output is correct
2 Correct 16 ms 9836 KB Output is correct
3 Correct 41 ms 23404 KB Output is correct
4 Correct 42 ms 23532 KB Output is correct
5 Correct 145 ms 23404 KB Output is correct
6 Correct 540 ms 21148 KB Output is correct
7 Correct 571 ms 22944 KB Output is correct
8 Correct 488 ms 23608 KB Output is correct
9 Correct 122 ms 23276 KB Output is correct
10 Correct 245 ms 21740 KB Output is correct
11 Correct 231 ms 21356 KB Output is correct
12 Correct 234 ms 21740 KB Output is correct
13 Correct 220 ms 18284 KB Output is correct
14 Correct 223 ms 18796 KB Output is correct
15 Correct 219 ms 18924 KB Output is correct
16 Correct 240 ms 15212 KB Output is correct
17 Correct 202 ms 15212 KB Output is correct
18 Correct 206 ms 15212 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6380 KB Output is correct
2 Correct 16 ms 9836 KB Output is correct
3 Correct 41 ms 23404 KB Output is correct
4 Correct 42 ms 23532 KB Output is correct
5 Correct 145 ms 23404 KB Output is correct
6 Correct 540 ms 21148 KB Output is correct
7 Correct 571 ms 22944 KB Output is correct
8 Correct 488 ms 23608 KB Output is correct
9 Correct 122 ms 23276 KB Output is correct
10 Correct 245 ms 21740 KB Output is correct
11 Correct 231 ms 21356 KB Output is correct
12 Correct 234 ms 21740 KB Output is correct
13 Correct 220 ms 18284 KB Output is correct
14 Correct 223 ms 18796 KB Output is correct
15 Correct 219 ms 18924 KB Output is correct
16 Correct 240 ms 15212 KB Output is correct
17 Correct 202 ms 15212 KB Output is correct
18 Correct 206 ms 15212 KB Output is correct
19 Correct 248 ms 118940 KB Output is correct
20 Correct 287 ms 135156 KB Output is correct
21 Execution timed out 9076 ms 94204 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 97360 KB Output is correct
2 Runtime error 1310 ms 524288 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 10 ms 6380 KB Output is correct
2 Correct 16 ms 9836 KB Output is correct
3 Correct 41 ms 23404 KB Output is correct
4 Correct 42 ms 23532 KB Output is correct
5 Correct 145 ms 23404 KB Output is correct
6 Correct 540 ms 21148 KB Output is correct
7 Correct 571 ms 22944 KB Output is correct
8 Correct 488 ms 23608 KB Output is correct
9 Correct 122 ms 23276 KB Output is correct
10 Correct 245 ms 21740 KB Output is correct
11 Correct 231 ms 21356 KB Output is correct
12 Correct 234 ms 21740 KB Output is correct
13 Correct 220 ms 18284 KB Output is correct
14 Correct 223 ms 18796 KB Output is correct
15 Correct 219 ms 18924 KB Output is correct
16 Correct 240 ms 15212 KB Output is correct
17 Correct 202 ms 15212 KB Output is correct
18 Correct 206 ms 15212 KB Output is correct
19 Correct 248 ms 118940 KB Output is correct
20 Correct 287 ms 135156 KB Output is correct
21 Execution timed out 9076 ms 94204 KB Time limit exceeded
22 Halted 0 ms 0 KB -