Submission #1261860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261860		g4yuhg	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1606 ms	167648 KiB

bubblesort2

//Huyduocdithitp

//bubble sort + nghịch thế: số lần bubble sort = i - (số phần tử < ai trong cả dãy)
// ta dung segment tree + lazy quản lý điều này

#include <bits/stdc++.h>
#include "bubblesort2.h"
typedef int ll;
#define pii pair<ll, ll> 
#define MP make_pair
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 500005
#define M 1000006
#define LOG 18
#define endl '\n'
using namespace std;
 
bool ghuy4g;

ll S;

ll n, q, a[N], m, st[6 * M], f[6 * M];
pii qr[N];

vector<pii> ns;

set<ll> s[2000006];

ll bit[M * 2];

void upd(ll u, ll v) {
	ll idx = u;
	while (idx <= m) {
		bit[idx] += v;
		idx += idx & (-idx);
	}
}

ll get(ll u) {
	ll idx = u, ans = 0;
	while (idx > 0) {
		ans += bit[idx];
		idx -= idx & (-idx);
	}
	return ans;
}

ll gm(ll id) {
	if (s[id].size() == 0) return 0;
	else return *s[id].rbegin();
}

void build(ll id, ll l, ll r) {
	if (l == r) {
		st[id] = gm(l) - 1 - get(l - 1);
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = max(st[id * 2], st[id * 2 + 1]);
}

void pre() {
	sort(ns.begin(), ns.end());
	ns.resize(unique(ns.begin(), ns.end()) - ns.begin());
	m = ns.size();
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(ns.begin(), ns.end(), make_pair(a[i], i)) - ns.begin() + 1;
		upd(a[i], 1);
		//cout << a[i] << " ";
		s[a[i]].insert(i);
	}
	//cout << endl;
	for (int i = 1; i <= q; i ++) {
		qr[i].se = lower_bound(ns.begin(), ns.end(), make_pair(qr[i].se, qr[i].fi)) - ns.begin() + 1;
		//cout << qr[i].fi << " " << qr[i].se << endl;
	}
	build(1, 1, m);
}

void lazy(ll id) {
	if (f[id] == 0) return;
	st[id] += f[id];
	if (id * 2 < 4 * N) {
		f[id * 2] += f[id];
	}
	if (id * 2 + 1 < 4 * N) {
		f[id * 2 + 1] += f[id];
	}
	f[id] = 0;
}

void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	lazy(id);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] += v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = max(st[id * 2], st[id * 2 + 1]);
}

void update1(ll id, ll l, ll r, ll i, ll v) {
	lazy(id);
	if (i > r || i < l || l > r) return;
	if (l == r) {
		st[id] = v;
		return;
	}
	ll mid = (l + r) / 2;
	update1(id * 2, l, mid, i, v);
	update1(id * 2 + 1, mid + 1, r, i, v);
	st[id] = max(st[id * 2], st[id * 2 + 1]);
}

vector<int> answer;

void solve() {
	for (int id = 1; id <= q; id ++) {
		ll i = qr[id].fi, v = qr[id].se;
		ll o_v = a[i], n_v = v;
		a[i] = n_v;
		if (o_v == n_v) {
			//cout << max(0, st[1]) << endl;
			answer.push_back(max(0, st[1]));
			continue;
		}
		//cout << i << " " << o_v << " " << n_v << endl;
		upd(o_v, -1);
		upd(n_v, 1);
		s[o_v].erase(i);
		update1(1, 1, m, o_v, gm(o_v) - get(o_v - 1) - 1);
		s[n_v].insert(i);
		update1(1, 1, m, n_v, gm(n_v) - get(n_v - 1) - 1);
		if (o_v < n_v) {
			// o_v + 1 -> n_v - 1
			update(1, 1, m, o_v + 1, n_v - 1, 1);
		}
		else {
			update(1, 1, m, n_v + 1, o_v - 1, -1);
		}
		//cout << max(0, st[1]) << endl;
		answer.push_back(max(0, st[1]));
	}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	//cin >> n >> q;
	n = A.size(), q = X.size();
	for (int i = 1; i <= n; i ++) {
		//cin >> a[i];
		a[i] = A[i - 1];
		ns.push_back({a[i], i});
	}
	for (int i = 1; i <= q; i ++) {
		//cin >> qr[i].fi >> qr[i].se;
		qr[i].fi = X[i - 1];
		qr[i].se = V[i - 1];
		qr[i].fi ++ ;
		//cout << qr[i].fi << " | " << qr[i].se << endl;
		ns.push_back({qr[i].se, qr[i].fi});
	}
	pre();
	solve();
	return answer;
}

bool klinh;

/*signed main(void) {
	faster;
	
	//countScans();
	
	cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
	
	return 0;
}*/

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