Submission #1139011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139011		mnbvcxz123	Swap Swap Sort (CCO21_day1problem1)	C++20	5 / 25	216 ms	18704 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 1e5+5,MV = 1e3+5;
int n,k,q,a[MM],p[MM],bit[MM],mp[MM]; vector<int> pos[MM];

void upd(int x, int v){
	for(; x < MM; x += x & -x) bit[x] += v;
}

int get(int x){
	int res = 0;
	for(; x > 0; x -= x & -x) res += bit[x];
	return res;
}

ll inv[MV][MV],ainv[MV][MV];
int cnt[MV];
int main(){
	cin.tie(0)->sync_with_stdio(0);	
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++) cin >> a[i],pos[a[i]].emplace_back(i);
	iota(p,p+1+k,0);
	for(int i = 1; i <= k; i++) mp[p[i]] = i;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= k; j++){
				inv[j][a[i]] += cnt[j];
			}
			cnt[a[i]]++;
		}
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			ans += get(k) - get(mp[a[i]]);
			upd(mp[a[i]],1);
		}
		while(q--){
			int j; cin >> j;
			ll old = inv[p[j+1]][p[j]];
			ll nw = inv[p[j]][p[j+1]];
			mp[p[j]] = j+1;
			mp[p[j+1]] = j;
			swap(p[j],p[j+1]);
			ans += nw - old;
			cout << ans << "\n";
		}
}

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