oj.uz

Submission #364448

# Submission time Handle Problem Language Result Execution time Memory
364448 2021-02-09T07:59:16 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 3308 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)
	{
		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]);
	}
	for (int i = 0; i < n; ++i)
		sort(T[i].begin(), T[i].end());
	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(2*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:231:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  231 |   for (int j = 0; j < Q; j++)
      |   ^~~
bubblesort2.cpp:232:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  232 |    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 49 ms 384 KB Output is correct
2 Correct 113 ms 364 KB Output is correct
3 Correct 720 ms 492 KB Output is correct
4 Correct 729 ms 596 KB Output is correct
5 Correct 818 ms 596 KB Output is correct
6 Correct 928 ms 596 KB Output is correct
7 Correct 1020 ms 492 KB Output is correct
8 Correct 1026 ms 492 KB Output is correct
9 Correct 789 ms 492 KB Output is correct
10 Correct 797 ms 492 KB Output is correct
11 Correct 738 ms 620 KB Output is correct
12 Correct 737 ms 620 KB Output is correct
13 Correct 726 ms 512 KB Output is correct
14 Correct 731 ms 620 KB Output is correct
15 Correct 727 ms 620 KB Output is correct
16 Correct 743 ms 620 KB Output is correct
17 Correct 714 ms 620 KB Output is correct
18 Correct 719 ms 620 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB Output is correct
2 Correct 113 ms 364 KB Output is correct
3 Correct 720 ms 492 KB Output is correct
4 Correct 729 ms 596 KB Output is correct
5 Correct 818 ms 596 KB Output is correct
6 Correct 928 ms 596 KB Output is correct
7 Correct 1020 ms 492 KB Output is correct
8 Correct 1026 ms 492 KB Output is correct
9 Correct 789 ms 492 KB Output is correct
10 Correct 797 ms 492 KB Output is correct
11 Correct 738 ms 620 KB Output is correct
12 Correct 737 ms 620 KB Output is correct
13 Correct 726 ms 512 KB Output is correct
14 Correct 731 ms 620 KB Output is correct
15 Correct 727 ms 620 KB Output is correct
16 Correct 743 ms 620 KB Output is correct
17 Correct 714 ms 620 KB Output is correct
18 Correct 719 ms 620 KB Output is correct
19 Execution timed out 9049 ms 1132 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB Output is correct
2 Correct 113 ms 364 KB Output is correct
3 Correct 720 ms 492 KB Output is correct
4 Correct 729 ms 596 KB Output is correct
5 Correct 818 ms 596 KB Output is correct
6 Correct 928 ms 596 KB Output is correct
7 Correct 1020 ms 492 KB Output is correct
8 Correct 1026 ms 492 KB Output is correct
9 Correct 789 ms 492 KB Output is correct
10 Correct 797 ms 492 KB Output is correct
11 Correct 738 ms 620 KB Output is correct
12 Correct 737 ms 620 KB Output is correct
13 Correct 726 ms 512 KB Output is correct
14 Correct 731 ms 620 KB Output is correct
15 Correct 727 ms 620 KB Output is correct
16 Correct 743 ms 620 KB Output is correct
17 Correct 714 ms 620 KB Output is correct
18 Correct 719 ms 620 KB Output is correct
19 Execution timed out 9049 ms 1132 KB Time limit exceeded
20 Halted 0 ms 0 KB -