oj.uz

Submission #364444

# Submission time Handle Problem Language Result Execution time Memory
364444 2021-02-09T07:41:43 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 4868 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;
}

vector<int> merge(const vector<int> &a, const vector<int> &b)
{
	int i, j, k;
	vector<int> res(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];
	return res;
}

static int smart2(const vector<int> &A)
{
	int n = A.size();
	int res = 0;
	int p = int(2e9);
	vector<vector<int>> T(2*n);
	for (int i = 0; i < n; ++i)
	{
		T[i+n].assign(1, A[i]);
	}
	for (int i = n - 1; i > 0; --i)
		T[i] = merge(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;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();
	int N = A.size();
	vector<int> answer(Q);
	for (int j = 0; j < Q; ++j)
	{
		A[X[j]] = V[j];
		answer[j] = smart2(A);
	}
	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 'std::vector<int> merge(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:205:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  205 |   for (int j = 0; j < Q; j++)
      |   ^~~
bubblesort2.cpp:206:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  206 |    V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
      |                                                                   ^~~~~~
bubblesort2.cpp: At global scope:
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 43 ms 364 KB Output is correct
2 Correct 104 ms 364 KB Output is correct
3 Correct 675 ms 748 KB Output is correct
4 Correct 633 ms 692 KB Output is correct
5 Correct 717 ms 620 KB Output is correct
6 Correct 1016 ms 692 KB Output is correct
7 Correct 1038 ms 748 KB Output is correct
8 Correct 998 ms 748 KB Output is correct
9 Correct 689 ms 692 KB Output is correct
10 Correct 835 ms 748 KB Output is correct
11 Correct 776 ms 748 KB Output is correct
12 Correct 790 ms 748 KB Output is correct
13 Correct 768 ms 620 KB Output is correct
14 Correct 778 ms 716 KB Output is correct
15 Correct 797 ms 620 KB Output is correct
16 Correct 768 ms 748 KB Output is correct
17 Correct 787 ms 748 KB Output is correct
18 Correct 774 ms 692 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 364 KB Output is correct
2 Correct 104 ms 364 KB Output is correct
3 Correct 675 ms 748 KB Output is correct
4 Correct 633 ms 692 KB Output is correct
5 Correct 717 ms 620 KB Output is correct
6 Correct 1016 ms 692 KB Output is correct
7 Correct 1038 ms 748 KB Output is correct
8 Correct 998 ms 748 KB Output is correct
9 Correct 689 ms 692 KB Output is correct
10 Correct 835 ms 748 KB Output is correct
11 Correct 776 ms 748 KB Output is correct
12 Correct 790 ms 748 KB Output is correct
13 Correct 768 ms 620 KB Output is correct
14 Correct 778 ms 716 KB Output is correct
15 Correct 797 ms 620 KB Output is correct
16 Correct 768 ms 748 KB Output is correct
17 Correct 787 ms 748 KB Output is correct
18 Correct 774 ms 692 KB Output is correct
19 Correct 8681 ms 1608 KB Output is correct
20 Execution timed out 9027 ms 1748 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9046 ms 4868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 364 KB Output is correct
2 Correct 104 ms 364 KB Output is correct
3 Correct 675 ms 748 KB Output is correct
4 Correct 633 ms 692 KB Output is correct
5 Correct 717 ms 620 KB Output is correct
6 Correct 1016 ms 692 KB Output is correct
7 Correct 1038 ms 748 KB Output is correct
8 Correct 998 ms 748 KB Output is correct
9 Correct 689 ms 692 KB Output is correct
10 Correct 835 ms 748 KB Output is correct
11 Correct 776 ms 748 KB Output is correct
12 Correct 790 ms 748 KB Output is correct
13 Correct 768 ms 620 KB Output is correct
14 Correct 778 ms 716 KB Output is correct
15 Correct 797 ms 620 KB Output is correct
16 Correct 768 ms 748 KB Output is correct
17 Correct 787 ms 748 KB Output is correct
18 Correct 774 ms 692 KB Output is correct
19 Correct 8681 ms 1608 KB Output is correct
20 Execution timed out 9027 ms 1748 KB Time limit exceeded
21 Halted 0 ms 0 KB -