oj.uz

Submission #364446

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

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(2*N);
	for (int j = 0; j < Q; ++j)
	{
		A[X[j]] = V[j];
		answer[j] = smart2(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:202:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  202 |   for (int j = 0; j < Q; j++)
      |   ^~~
bubblesort2.cpp:203:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  203 |    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 19 ms 364 KB Output is correct
2 Correct 38 ms 492 KB Output is correct
3 Correct 257 ms 620 KB Output is correct
4 Correct 264 ms 748 KB Output is correct
5 Correct 377 ms 748 KB Output is correct
6 Correct 683 ms 748 KB Output is correct
7 Correct 666 ms 620 KB Output is correct
8 Correct 628 ms 820 KB Output is correct
9 Correct 358 ms 748 KB Output is correct
10 Correct 413 ms 748 KB Output is correct
11 Correct 409 ms 748 KB Output is correct
12 Correct 407 ms 620 KB Output is correct
13 Correct 419 ms 620 KB Output is correct
14 Correct 405 ms 620 KB Output is correct
15 Correct 415 ms 748 KB Output is correct
16 Correct 404 ms 692 KB Output is correct
17 Correct 405 ms 748 KB Output is correct
18 Correct 405 ms 620 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 364 KB Output is correct
2 Correct 38 ms 492 KB Output is correct
3 Correct 257 ms 620 KB Output is correct
4 Correct 264 ms 748 KB Output is correct
5 Correct 377 ms 748 KB Output is correct
6 Correct 683 ms 748 KB Output is correct
7 Correct 666 ms 620 KB Output is correct
8 Correct 628 ms 820 KB Output is correct
9 Correct 358 ms 748 KB Output is correct
10 Correct 413 ms 748 KB Output is correct
11 Correct 409 ms 748 KB Output is correct
12 Correct 407 ms 620 KB Output is correct
13 Correct 419 ms 620 KB Output is correct
14 Correct 405 ms 620 KB Output is correct
15 Correct 415 ms 748 KB Output is correct
16 Correct 404 ms 692 KB Output is correct
17 Correct 405 ms 748 KB Output is correct
18 Correct 405 ms 620 KB Output is correct
19 Correct 4160 ms 1604 KB Output is correct
20 Correct 5453 ms 1772 KB Output is correct
21 Execution timed out 9092 ms 1644 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5000 ms 4976 KB Output is correct
2 Execution timed out 9037 ms 7404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 364 KB Output is correct
2 Correct 38 ms 492 KB Output is correct
3 Correct 257 ms 620 KB Output is correct
4 Correct 264 ms 748 KB Output is correct
5 Correct 377 ms 748 KB Output is correct
6 Correct 683 ms 748 KB Output is correct
7 Correct 666 ms 620 KB Output is correct
8 Correct 628 ms 820 KB Output is correct
9 Correct 358 ms 748 KB Output is correct
10 Correct 413 ms 748 KB Output is correct
11 Correct 409 ms 748 KB Output is correct
12 Correct 407 ms 620 KB Output is correct
13 Correct 419 ms 620 KB Output is correct
14 Correct 405 ms 620 KB Output is correct
15 Correct 415 ms 748 KB Output is correct
16 Correct 404 ms 692 KB Output is correct
17 Correct 405 ms 748 KB Output is correct
18 Correct 405 ms 620 KB Output is correct
19 Correct 4160 ms 1604 KB Output is correct
20 Correct 5453 ms 1772 KB Output is correct
21 Execution timed out 9092 ms 1644 KB Time limit exceeded
22 Halted 0 ms 0 KB -