Submission #1102260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102260		vjudge1	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	2847 ms	102116 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
const ll lg = 20;
ll n,k,q;
ll a[N], p[N];
vector<ll>pos[N];
map<pll,ll>ans;
struct fenwick_tree{
	ll n;
	vector<ll>ft;
	void init(ll _n){
		n = _n;
		ft.resize(n + 10);
	}
	void update(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 sum(ll l, ll r){
        if(l > r) return 0;
        return get(r) - get(l - 1);
    }
} ft;
ll calc(ll x, ll y){
    if(ans.find({x, y}) != ans.end()) return ans[{x, y}];
    if(pos[x].size() > pos[y].size()) return (ll)pos[x].size() * (ll)pos[y].size() - calc(y, x);
    ll cnt = 0;
    for(auto i : pos[x]){
        ll j = upper_bound(all(pos[y]), i) - pos[y].begin();
        cnt += (ll)pos[y].size() - j;
    }
    ans[{x, y}] = cnt;
    return cnt;
}
void to_thic_cau(){
    cin >> n >> k >> q;
    for(int i = 1; i <= n;i++){
        cin >> a[i];
        pos[a[i]].pb(i);
    }
    for(int i = 1; i <= k;i++) p[i] = i;
    ft.init(n);
    ll res = 0;
    for(int i = 1; i <= n;i++){
        ft.update(a[i], 1);
        res += ft.sum(a[i] + 1, n);
    }
    while(q--){
        ll i; cin >> i;
        res -= calc(p[i+1], p[i]);  
        res += calc(p[i], p[i+1]);
        swap(p[i], p[i+1]);
        cout << res << "\n";
    }
}   

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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