Submission #379267

#	Time	Username	Problem	Language	Result	Execution time	Memory
379267		qwerty234	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	481 ms	908 KiB

bubblesort2

#include "bubblesort2.h"
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;

vector <int> countScans(vector <int> a, vector <int> x, vector <int> v) {
	int n = a.size(), q = x.size();
	if (n > 8000 || q > 8000)
		return {};
	vector <int> cnt, anss = {}; cnt.assign(n, 0);
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (a[i] > a[j])
				cnt[j]++;
	for (int i = 0; i < q; i++) {
		int pos = x[i], val = v[i];
		for (int j = pos + 1; j < n; j++)
			if (a[pos] <= a[j] && a[j] < val)
				cnt[j]++;
			else if (val <= a[j] && a[j] < a[pos])
				cnt[j]--;
		cnt[pos] = 0;
		for (int j = 0; j < pos; j++)
			if (a[j] > val)
				cnt[pos]++;
		a[pos] = val;
		int ans = 0;
		for (int j = 0; j < n; j++)
			ans = max(ans, cnt[j]);
		anss.pb(ans);
	}
	return anss;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40