Submission #1268265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268265		MisterReaper	Bubble Sort 2 (JOI18_bubblesort2)	C++20	38 / 100	10 ms	1864 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int inf = int(1E9);

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
	int n;
	std::vector<std::set<int>> ids;
	std::vector<int> tree, cnt;
	segtree(int n_) : n(n_), ids(n), tree(n << 1), cnt(n << 1) {}
	void pull(int v, int l, int r) {
		def;
		tree[v] = std::max(tree[lv], tree[rv] - cnt[lv]);
		cnt[v] = cnt[lv] + cnt[rv];
	}
	void modify(int v, int l, int r, int p, int x, int c) {
		debug(v, l, r, p, x, c);
		if (l == r) {
			cnt[v] = c;
			tree[v] = x - c + 1;
			return;
		}
		def;
		if (p <= mid) {
			modify(lv, l, mid, p, x, c);
		} else {
			modify(rv, mid + 1, r, p, x, c);
		}
		debug(1);
		pull(v, l, r);
	}
	void modify(int p, int x, int c) {
		modify(0, 0, n - 1, p, x, c);
	}
	void insert(int p, int x) {
		ids[p].emplace(x);
		modify(p, *ids[p].rbegin(), ids[p].size());
	}
	void erase(int p, int x) {
		ids[p].erase(x);
		modify(p, ids[p].empty() ? -inf : *ids[p].begin(), ids[p].size());
	}
};

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
	std::vector<int> ids(A.begin(), A.end());
	ids.insert(ids.end(), V.begin(), V.end());
	std::sort(ids.begin(), ids.end());
	int n;
	ids.resize(n = int(std::unique(ids.begin(), ids.end()) - ids.begin()));
	
	segtree seg(n);

	int N = int(A.size());
	int Q = int(X.size());

	debug(1);

	for (int i = 0; i < N; ++i) {
		A[i] = int(std::lower_bound(ids.begin(), ids.end(), A[i]) - ids.begin());
		seg.insert(A[i], i);
	}
	for (int i = 0; i < Q; ++i) {
		V[i] = int(std::lower_bound(ids.begin(), ids.end(), V[i]) - ids.begin());
	}

	debug(2);

	std::vector<int> ans(Q);
	for (int i = 0; i < Q; ++i) {
		seg.erase(A[X[i]], X[i]);
		A[X[i]] = V[i];
		seg.insert(A[X[i]], X[i]);
		ans[i] = seg.tree[0];
	}

	return ans;
}

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