oj.uz

Submission #364462

# Submission time Handle Problem Language Result Execution time Memory
364462 2021-02-09T08:53:28 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 5352 KB 
#include "bubblesort2.h"
#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;
}

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<vector<int>> T(N);
	for (int j = 0; j < Q; ++j)
	{
		A[X[j]] = V[j];
		answer[j] = smart3(A, T);
	}
	return answer;
	vector<int> all(N + Q);
	for (int i = 0; i < N; ++i)
		all[i] = A[i];
	for (int i = 0; i < Q; ++i)
		all[N+i] = V[i];
	sort(all.begin(), all.end());
	vector<int>::iterator z = unique(all.begin(), all.end());
	all.resize(z - all.begin());
	/*for (int j = 0; j < all.size(); ++j)
		printf("%d ", all[j]);
	printf("\n");*/
	if (all.back() <= 100)
	{
		vector<int> T[101];
		for (int x = 0; x <= 100; ++x)
			T[x].resize(2*N);
		for (int j = 0; j < N; ++j) 
			for (int x = A[j] - 1; x >= 0; --x)
				add(T[x], j, 1);
		set<int> pos[101];
		for (int j = 0; j < N; ++j) 
			pos[A[j]].insert(-j);
		for (int j = 0; j < Q; j++)
		{
			int p = X[j];
			for (int x = A[p] - 1; x >= 0; --x)
			{
				add(T[x], p, -1);
			}
			pos[A[p]].erase(-p);
			A[p] = V[j];
			for (int x = V[j] - 1; x >= 0; --x)
				add(T[x], p, 1);
			pos[V[j]].insert(-p);
			int ans = 0;
			for (int x = 0; x <= 100; ++x)
				if (pos[x].size())
				{
					ans = max(ans, get(T[x], -*(pos[x].begin())));
				}
			answer[j] = ans;
		}
	}
	else
	{
		for (int j = 0; j < N; j++)
			A[j] = lower_bound(all.begin(), all.end(), A[j]) - all.begin();
		for (int j = 0; j < Q; j++)
			V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
		for (int j = 0; j < Q; j++)
		{
			A[X[j]] = V[j];
			answer[j] = smart(A, F, all);
		}
	}
	return answer;
}

Compilation message

bubblesort2.cpp: In function 'void add(std::vector<int>&, int, int)':
bubblesort2.cpp:40:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  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:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for (i = 0, j = 0; i < a.size() && j < b.size(); )
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:98:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for (i = 0, j = 0; i < a.size() && j < b.size(); )
      |                                     ~~^~~~~~~~~~
bubblesort2.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (; i < a.size(); ++i, ++k)
      |         ~~^~~~~~~~~~
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 (; j < b.size(); ++j, ++k)
      |         ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:242:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  242 |   for (int j = 0; j < Q; j++)
      |   ^~~
bubblesort2.cpp:243:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  243 |    V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
      |                                                                   ^~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:111:12: warning: 'int smart2(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
  111 | static int smart2(const vector<int> &A, vector<vector<int>> &T)
      |            ^~~~~~
bubblesort2.cpp:73:12: warning: 'int smart1(const std::vector<int>&)' defined but not used [-Wunused-function]
   73 | static int smart1(const vector<int> &A)
      |            ^~~~~~
bubblesort2.cpp:44:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
   44 | static int stupid1(vector<int> A)
      |            ^~~~~~~
bubblesort2.cpp:7:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
    7 | static int stupid(vector<int> A)
      |            ^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 492 KB Output is correct
2 Correct 62 ms 364 KB Output is correct
3 Correct 360 ms 608 KB Output is correct
4 Correct 357 ms 620 KB Output is correct
5 Correct 433 ms 492 KB Output is correct
6 Correct 649 ms 620 KB Output is correct
7 Correct 678 ms 608 KB Output is correct
8 Correct 657 ms 620 KB Output is correct
9 Correct 405 ms 620 KB Output is correct
10 Correct 465 ms 620 KB Output is correct
11 Correct 463 ms 492 KB Output is correct
12 Correct 493 ms 620 KB Output is correct
13 Correct 466 ms 492 KB Output is correct
14 Correct 464 ms 492 KB Output is correct
15 Correct 480 ms 620 KB Output is correct
16 Correct 480 ms 620 KB Output is correct
17 Correct 466 ms 620 KB Output is correct
18 Correct 477 ms 620 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 492 KB Output is correct
2 Correct 62 ms 364 KB Output is correct
3 Correct 360 ms 608 KB Output is correct
4 Correct 357 ms 620 KB Output is correct
5 Correct 433 ms 492 KB Output is correct
6 Correct 649 ms 620 KB Output is correct
7 Correct 678 ms 608 KB Output is correct
8 Correct 657 ms 620 KB Output is correct
9 Correct 405 ms 620 KB Output is correct
10 Correct 465 ms 620 KB Output is correct
11 Correct 463 ms 492 KB Output is correct
12 Correct 493 ms 620 KB Output is correct
13 Correct 466 ms 492 KB Output is correct
14 Correct 464 ms 492 KB Output is correct
15 Correct 480 ms 620 KB Output is correct
16 Correct 480 ms 620 KB Output is correct
17 Correct 466 ms 620 KB Output is correct
18 Correct 477 ms 620 KB Output is correct
19 Correct 5489 ms 1260 KB Output is correct
20 Correct 7189 ms 1388 KB Output is correct
21 Execution timed out 9021 ms 1536 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6787 ms 2924 KB Output is correct
2 Execution timed out 9099 ms 5352 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 492 KB Output is correct
2 Correct 62 ms 364 KB Output is correct
3 Correct 360 ms 608 KB Output is correct
4 Correct 357 ms 620 KB Output is correct
5 Correct 433 ms 492 KB Output is correct
6 Correct 649 ms 620 KB Output is correct
7 Correct 678 ms 608 KB Output is correct
8 Correct 657 ms 620 KB Output is correct
9 Correct 405 ms 620 KB Output is correct
10 Correct 465 ms 620 KB Output is correct
11 Correct 463 ms 492 KB Output is correct
12 Correct 493 ms 620 KB Output is correct
13 Correct 466 ms 492 KB Output is correct
14 Correct 464 ms 492 KB Output is correct
15 Correct 480 ms 620 KB Output is correct
16 Correct 480 ms 620 KB Output is correct
17 Correct 466 ms 620 KB Output is correct
18 Correct 477 ms 620 KB Output is correct
19 Correct 5489 ms 1260 KB Output is correct
20 Correct 7189 ms 1388 KB Output is correct
21 Execution timed out 9021 ms 1536 KB Time limit exceeded
22 Halted 0 ms 0 KB -