Submission #1272701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272701		pvb.tunglam	Swap Swap Sort (CCO21_day1problem1)	C++20	25 / 25	4470 ms	43232 KiB

Main

#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll oo = 8e18;

ll powder(ll a, ll b) {
	if (b == 0) return 1;
	ll half = powder(a, b/2);
	if (b & 1) return ((half * half) % MOD * a) % MOD;
	return (half * half) % MOD;
}

/*----------- I alone decide my fate! ----------*/
   /* Chiec den ong sao, sao 5 canh tuoi mau */

const int threshold = 600;   
int N, K, Q, cnt[100009], p[1000009], heav[100009], a[100009];
vector <int> pos[100009];
ll inv[359][100009], curAns = 0;

ll calc(int x, int y) {
	int n = (int)pos[x].size(), m = (int)pos[y].size();
	if (x == y) return 0;
	if (heav[x]) return inv[heav[x]][y];
	if (heav[y]) {
		return 1ll * n * m - inv[heav[y]][x];
	}
	if (m == 0 || n == 0) return 0;
	int pt = 0;
	ll ret = 0;
	for (int i = 0; i < n; i ++) {
		while (pt < m && pos[x][i] > pos[y][pt]) {
			pt ++;
		}
		ret += m - pt;
	}
	return ret;
}

int bit[100009];

void update(int x) {
	while (x) {
		bit[x] ++;
		x -= x &- x;
	} 
}

int get(int x) {
	int ret = 0;
	while (x <= K) {
		ret += bit[x];
		x += x &- x;
	}
	return ret;
}

void solve() {
	cin >> N >> K >> Q;
	for (int i = 1; i <= N; i ++) {
		cin >> a[i];
		cnt[a[i]] ++;
		pos[a[i]].push_back(i);
	}
	
	// heavy
	int numHeavy = 0;
	for (int i = 1; i <= K; i ++) {
		if (cnt[i] > threshold) {
			numHeavy ++;
			heav[i] = numHeavy;
			int cur = 0;
			for (int j = 1; j <= N; j ++) {
				cur += (a[j] == i);
				inv[numHeavy][a[j]] += cur;
			}
		}
	}	
	
	for (int i = 1; i <= N; i ++) {
		curAns += get(a[i] + 1);
		update(a[i]);
	}
	for (int i = 1; i <= N; i ++) p[i] = i;
	for (int i = 1; i <= Q; i ++) {
		int j; cin >> j;
		int x = p[j], y = p[j + 1];
		curAns += calc(x, y) - calc(y, x);
		swap(p[j], p[j + 1]);
		cout << curAns << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14