Submission #411594

#	Time	Username	Problem	Language	Result	Execution time	Memory
411594		thomas_li	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	1301 ms	22560 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

namespace std {
 
template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
 
	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};
 
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
 
} // namespace std
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; // get order in p
	if(k >= MV){
		// calc answer for no queries
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			ans += get(k) - get(mp[a[i]]); // [a[i]+1,k]
			upd(mp[a[i]],1);
		}
		//cout << ans << "\n";
		while(q--){
			int j; cin >> j;
			ll old = 0,nw = 0;
			int ptr = 0;
			if(pos[p[j]].size() < pos[p[j+1]].size()){
				for(int x : pos[p[j]]){
					while(ptr < (int)pos[p[j+1]].size() && pos[p[j+1]][ptr] < x){
						ptr++;
					}
					old += ptr;
					nw += (int)pos[p[j+1]].size() - ptr;
				}
			} else{
				for(int x : pos[p[j+1]]){
					while(ptr < (int)pos[p[j]].size() && pos[p[j]][ptr] < x){
						ptr++;
					}
					nw += ptr;
					old += (int)pos[p[j]].size() - ptr;
				}
			}
			mp[p[j]] = j+1;
			mp[p[j+1]] = j;
			swap(p[j],p[j+1]);
			//cout << nw << " " << old << "\n";
			ans += nw - old;
			cout << ans << "\n";
		}
	} else{
		// calculate fake inversions between each pair of colours
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= k; j++){
				inv[j][a[i]] += cnt[j]; // cur element will invert with all cnt[j] element
				// assume j value is > a[i]
			}
			cnt[a[i]]++;
		}
		//memset(cnt,0,sizeof cnt);
		/*
		// anti inversion (i < j and a[i] < a[j])
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= k; j++){
				ainv[j][a[i]] += cnt[j]; // cur element will invert with all cnt[j] element
				// assume j value is < a[i]
			}
			cnt[a[i]]++;
		}*/
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			ans += get(k) - get(mp[a[i]]); // [a[i]+1,k]
			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: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14