Submission #635762

#	Time	Username	Problem	Language	Result	Execution time	Memory
635762		jhnah917	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	2582 ms	85820 KiB

Main

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

int N, K, Q, A[101010], B[101010], T[101010];
vector<int> P[101010]; ll R;
void Add(int x, int v){ for(x+=3; x<101010; x+=x&-x) T[x] += v; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += T[x]; return ret; }

map<pair<int,int>, ll> Cache;
ll Swap(int u, int v){
    auto it = Cache.lower_bound(make_pair(u, v));
    if(it != Cache.end() && it->first == make_pair(u, v)) return it->second;

    ll res = 0;
    if(P[u].size() < P[v].size()){
        for(auto i : P[u]){
            int cnt = P[v].end() - lower_bound(P[v].begin(), P[v].end(), i);
            res += cnt - ((int)P[v].size() - cnt);
        }
    }
    else{
        for(auto i : P[v]){
            int cnt = lower_bound(P[u].begin(), P[u].end(), i) - P[u].begin();
            res += cnt - ((int)P[u].size() - cnt);
        }
    }
    Cache.emplace_hint(it, make_pair(u, v), res);
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K >> Q; iota(B+1, B+K+1, 1);
    for(int i=1; i<=N; i++) cin >> A[i], P[A[i]].push_back(i);
    for(int i=N; i>=1; i--) R += Get(A[i]-1), Add(A[i], 1);
    for(int q=1; q<=Q; q++){
        int t; cin >> t;
        R += Swap(B[t], B[t+1]); swap(B[t], B[t+1]);
        cout << R << "\n";
    }
}

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