Submission #1102307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102307		vjudge1	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	4043 ms	150600 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2")
#include<bits/stdc++.h>
#define pll pair<long long, long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
#define lowbit(x) (x & (-x))
#define sigma main
using namespace std;

const long long inf = 1e18; 
const int mod = 1e9+7;
const int MAXN = 4e5+100;

#define int long long

struct fenwick_tree{
	#define ll long long
	ll n;
    vector<ll>ft;
    void init(ll _n){
        n = _n;
        ft.resize(n + 10);
    }
    void add(ll idx, ll val){
        while(idx <= n) ft[idx] = (ft[idx] + val), idx += (idx & (-idx));
    }
    ll get(ll idx){
        ll res = 0;
        while(idx > 0) res = (res + ft[idx]), idx -= (idx & (-idx));
        return res;
    }
    ll get(ll l, ll r){return get(r) - get(l - 1);} 
} T;

vector<int> pos[MAXN];
map<pll , int> mp;
int32_t sigma(){
  	//freopen("MILITARYTRAINING.inp", "r", stdin);
	//freopen("MILITARYTRAINING.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n , k , q; cin >> n >> k >> q;
	vector<int> a(n + 1);

	T.init(k + 1);
	int ans = 0;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i]; pos[a[i]].push_back(i);
		if(a[i] < k) ans += T.get(a[i] + 1 , k);
		T.add(a[i] , 1);
	}

	vector<int> K(k + 1);
	for(int i = 1 ; i <= k ; i++) K[i] = i;
	while(q--){
		int j; cin >> j;
		int a = K[j] , b = K[j + 1];
		swap(K[j] , K[j+1]);

		if(mp.find({a , b}) != mp.end()){
			ans += mp[{a , b}];
			cout << ans << "\n"; continue;
		}
		int ab = 0 , ba = 0;
		if(pos[a].size() < pos[b].size()){
			for(auto x : pos[a]){
				int it = lower_bound(pos[b].begin() , pos[b].end() , x) - pos[b].begin();
				ba += it;
				ab += pos[b].size() - it;
			}
		}else{
			for(auto x : pos[b]){
				int it = lower_bound(pos[a].begin() , pos[a].end() , x) - pos[a].begin();
				ab += it;
				ba += pos[a].size() - it;
			}
		}

		ans -= ba ; ans += ab;
		cout << ans << "\n";
		mp[{a , b}] = -ba + ab;
		mp[{b , a}] = -ab + ba;
	}

	return 0;
}

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