Submission #711834

#	Time	Username	Problem	Language	Result	Execution time	Memory
711834		rainboy	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	5056 ms	52544 KiB

bubblesort2

#include "bubblesort2.h"

using namespace std;

typedef vector<int> vi;

const int N = 500000, Q = 500000, N_ = N + Q + 1;

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int aa[N];
int zz[N_ + 1], ll[N_ + 1], rr[N_ + 1], ii[N_ + 1], sz[N_ + 1], xx[N_ + 1], _, u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	sz[_] = 1;
	xx[_] = i + 1;
	return _++;
}

void pul(int u) {
	int l = ll[u], r = rr[u];

	sz[u] = sz[l] + 1 + sz[r];
	xx[u] = max(max(xx[l], ii[u]) + 1 + sz[r], xx[r]);
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = aa[ii[u]] != aa[i] ? aa[ii[u]] - aa[i] : ii[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

void tr_remove(int i) {
	split(u_, i);
	u_ = merge(l_, r_);
}

vi countScans(vi aa_, vi ii, vi bb) {
	int n = aa_.size();
	for (int i = 0; i < n; i++)
		aa[i] = aa_[i];
	for (int i = 0; i < n; i++)
		tr_add(i);
	int q = ii.size();
	vi ans(q);
	for (int h = 0; h < q; h++) {
		int i = ii[h], b = bb[h];
		tr_remove(i);
		aa[i] = b;
		tr_add(i);
		ans[h] = xx[u_] - n;
	}
	return ans;
}

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