Submission #652093

#	Time	Username	Problem	Language	Result	Execution time	Memory
652093		ymm	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	31 ms	39716 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

mt19937_64 rd(time(0));

const int N = 500'010;
struct node {
	node *l, *r;
	ll weight;
	pii key;
	int sz;
	int mx;
} pool[2*N];

node *new_node()
{
	static int nxt = 0;
	assert(nxt < 2*N);
	pool[nxt].weight = rd();
	return &pool[nxt++];
}

void up(node *t)
{
	t->mx = t->key.second - (t->l? t->l->sz: 0);
	t->mx = max(t->mx, t->l? t->l->mx: 0);
	t->mx = max(t->mx, t->r? t->r->mx - (t->l? t->l->sz: 0) - 1: 0);
	t->sz = 1 + (t->l? t->l->sz: 0) + (t->r? t->r->sz: 0);
}

node *merge(node *l, node *r)
{
	if (!l)
		return r;
	if (!r)
		return l;
	if (l->weight > r->weight) {
		l->r = merge(l->r, r);
		up(l);
		return l;
	} else {
		r->l = merge(l, r->l);
		up(r);
		return r;
	}
}

pair<node *, node *> split(node *t, pii key)
{
	if (!t)
		return {};
	if (t->key < key) {
		auto [l, r] = split(t->r, key);
		t->r = l;
		return {t, r};
	} else {
		auto [l, r] = split(t->l, key);
		t->l = r;
		return {l, t};
	}
}

node *erase(node *t, pii key)
{
	auto [l, tmp1] = split(t, key);
	key.second++;
	auto [tmp2, r] = split(tmp1, key);
	return merge(l, r);
}

node *insert(node *t, pii key)
{
	node *v = new_node();
	v->key = key;
	up(v);
	auto [l, r] = split(t, key);
	node *tmp;
	tmp = merge(l, v);
	tmp = merge(tmp, r);
	return tmp;
}

int a[N];
node *treap;
int n, q;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	n = A.size();
	q = X.size();
	vector<int> ans;
	Loop (i,0,n) {
		a[i] = A[i];
		treap = insert(treap, {a[i], i});
	}
	Loop (i,0,q) {
		int p = X[i];
		treap = erase(treap, {a[p], p});
		a[p] = V[i];
		treap = insert(treap, {a[p], p});
		ans.push_back(treap->mx);
	}
	return ans;
}

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