oj.uz

Submission #363228

# Submission time Handle Problem Language Result Execution time Memory
363228 2021-02-05T10:11:12 Z r57shell Bubble Sort 2 (JOI18_bubblesort2) C++14
39 / 100
 9000 ms 45056 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 vector<int> idx;

static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
{
	int n = A.size();
	int res = 0;
	idx.resize(A.size());
	for (int i = 0; i < n; ++i)
	{
		int id = lower_bound(all.begin(), all.end(), A[i]) - all.begin();
		idx[i] = id;
		//printf("%d %d\n", id, i - get(F, id));
		res = max(res, i - get(F, id));
		add(F, id, 1);
	}
	for (int i = 0; i < n; ++i)
		add(F, idx[i], -1);
	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<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
	{
		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: At global scope:
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 24 ms 492 KB Output is correct
2 Correct 61 ms 364 KB Output is correct
3 Correct 459 ms 364 KB Output is correct
4 Correct 466 ms 500 KB Output is correct
5 Correct 441 ms 620 KB Output is correct
6 Correct 356 ms 500 KB Output is correct
7 Correct 388 ms 620 KB Output is correct
8 Correct 405 ms 620 KB Output is correct
9 Correct 438 ms 492 KB Output is correct
10 Correct 373 ms 492 KB Output is correct
11 Correct 375 ms 492 KB Output is correct
12 Correct 371 ms 492 KB Output is correct
13 Correct 371 ms 492 KB Output is correct
14 Correct 371 ms 492 KB Output is correct
15 Correct 375 ms 640 KB Output is correct
16 Correct 368 ms 492 KB Output is correct
17 Correct 368 ms 492 KB Output is correct
18 Correct 375 ms 492 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 492 KB Output is correct
2 Correct 61 ms 364 KB Output is correct
3 Correct 459 ms 364 KB Output is correct
4 Correct 466 ms 500 KB Output is correct
5 Correct 441 ms 620 KB Output is correct
6 Correct 356 ms 500 KB Output is correct
7 Correct 388 ms 620 KB Output is correct
8 Correct 405 ms 620 KB Output is correct
9 Correct 438 ms 492 KB Output is correct
10 Correct 373 ms 492 KB Output is correct
11 Correct 375 ms 492 KB Output is correct
12 Correct 371 ms 492 KB Output is correct
13 Correct 371 ms 492 KB Output is correct
14 Correct 371 ms 492 KB Output is correct
15 Correct 375 ms 640 KB Output is correct
16 Correct 368 ms 492 KB Output is correct
17 Correct 368 ms 492 KB Output is correct
18 Correct 375 ms 492 KB Output is correct
19 Correct 7357 ms 856 KB Output is correct
20 Execution timed out 9015 ms 876 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 23788 KB Output is correct
2 Correct 390 ms 35088 KB Output is correct
3 Correct 673 ms 44652 KB Output is correct
4 Correct 684 ms 44800 KB Output is correct
5 Correct 818 ms 45036 KB Output is correct
6 Correct 758 ms 44652 KB Output is correct
7 Correct 890 ms 44780 KB Output is correct
8 Correct 910 ms 44652 KB Output is correct
9 Correct 902 ms 44780 KB Output is correct
10 Correct 817 ms 44836 KB Output is correct
11 Correct 805 ms 44908 KB Output is correct
12 Correct 828 ms 44824 KB Output is correct
13 Correct 637 ms 45056 KB Output is correct
14 Correct 683 ms 44908 KB Output is correct
15 Correct 673 ms 44908 KB Output is correct
16 Correct 493 ms 44780 KB Output is correct
17 Correct 493 ms 44864 KB Output is correct
18 Correct 490 ms 44652 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 492 KB Output is correct
2 Correct 61 ms 364 KB Output is correct
3 Correct 459 ms 364 KB Output is correct
4 Correct 466 ms 500 KB Output is correct
5 Correct 441 ms 620 KB Output is correct
6 Correct 356 ms 500 KB Output is correct
7 Correct 388 ms 620 KB Output is correct
8 Correct 405 ms 620 KB Output is correct
9 Correct 438 ms 492 KB Output is correct
10 Correct 373 ms 492 KB Output is correct
11 Correct 375 ms 492 KB Output is correct
12 Correct 371 ms 492 KB Output is correct
13 Correct 371 ms 492 KB Output is correct
14 Correct 371 ms 492 KB Output is correct
15 Correct 375 ms 640 KB Output is correct
16 Correct 368 ms 492 KB Output is correct
17 Correct 368 ms 492 KB Output is correct
18 Correct 375 ms 492 KB Output is correct
19 Correct 7357 ms 856 KB Output is correct
20 Execution timed out 9015 ms 876 KB Time limit exceeded
21 Halted 0 ms 0 KB -