Submission #1287882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287882		KickingKun	Bubble Sort 2 (JOI18_bubblesort2)	C++20	60 / 100	7189 ms	5476 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

template <class T> bool minimize(T &a, T b) {
	if (a > b) return a = b, true;
	return false;
}

template <class T> bool maximize(T &a, T b) {
	if (a < b) return a = b, true;
	return false;
}

const int N = 5e5 + 2;

int n, q;
int a[N], x[N], v[N];

namespace sub2 {
	vector <int> solve() {
		vector <int> res;
		for (int _ = 0; _ < q; _++) {
			a[x[_]] = v[_];

			vector <int> b(a, a + n + 1); 
			sort (b.begin() + 1, b.end());
			int ans = 0;
			for (int i = 1; i <= n; i++) {
				int k = upper_bound(b.begin() + 1, b.end(), a[i]) - b.begin() - 1;
				maximize(ans, i - k);
			}
			res.emplace_back(ans);
		}
		return res;
	}
}

namespace sub3 {
	set <int> pos[102];
	vector <int> solve() {
		for (int i = 1; i <= 100; i++) pos[i].clear();
		for (int i = 1; i <= n; i++) pos[a[i]].emplace(i);

		vector <int> res;
		for (int _ = 0; _ < q; _++) {
			pos[a[x[_]]].erase(x[_]);
			a[x[_]] = v[_];
			pos[a[x[_]]].emplace(x[_]);

			int ans = 0, cnt = 0;
			for (int i = 1; i <= 100; i++) if (!pos[i].empty()) {
				cnt += pos[i].size();
				maximize(ans, *pos[i].rbegin() - cnt);
			}
			res.emplace_back(ans);
		}
		return res;
	}
}

namespace sub4 {
	vector <int> solve() {
		return {};
	}
}

vector <int> countScans(vector <int> A,vector <int> X, vector <int> V){
	n = A.size(); q = X.size();
	for (int i = 1; i <= n; i++) a[i] = A[i - 1];
	for (int i = 0; i < q; i++) x[i] = X[i] + 1, v[i] = V[i];

	if (max(A.size(), X.size()) <= 8e3) return sub2::solve();
	if (max(*max_element(A.begin(), A.end()), *max_element(V.begin(), V.end())) <= 100)
		return sub3::solve();
	return sub4::solve();
}

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