Submission #411675

#	Time	Username	Problem	Language	Result	Execution time	Memory
411675		Dormi	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	1984 ms	71212 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T>
int sz(const T &a){return int(a.size());}
const int MN=1e5+1,MB=100;
int arr[MN];
vector<int> locs[MN];
vector<ll> pc[MN];
int ind[MN];
int ord[MN];
ll bit[MN];
int n,k,q;
void update(int loc, ll val){
    for(;loc<=k;loc+=loc&-loc)bit[loc]+=val;
}
ll query(int loc){
    ll res=0;
    for(;loc>0;loc-=loc&-loc)res+=bit[loc];
    return res;
}
int main(int argc, char* argv[]){//bubble sort, count inversions. maintain number of adjacent inversions? sqrt is possible..
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>k>>q;
    ll tot=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        tot+=query(k)-query(arr[i]);
        update(arr[i],1);
        locs[arr[i]].push_back(i);
    }
    int am=0;
    for(int i=1;i<=k;i++){
        ord[i]=i;
        if(sz(locs[i])>=MB){
            ind[i]=am++;
            for(int j=1;j<=k;j++)pc[j].push_back(0);
            int cnt=0;
            for(int j=1;j<=n;j++){
                if(arr[j]==i)cnt++;
                else{
                    pc[arr[j]].back()+=cnt;
                }
            }
        }
    }
    auto calc=[&](int i){
        int cur=ord[i],pre=ord[i-1];
        ll res=0;
        if(sz(locs[cur])>=MB){
            res+=pc[pre][ind[cur]];
        }
        else if(sz(locs[pre])>=MB){
            res+=ll(sz(locs[pre]))*ll(sz(locs[cur]))-pc[cur][ind[pre]];
        }
        else{
            int ptr=0;
            for(auto x:locs[cur]){
                while(ptr!=sz(locs[pre])&&locs[pre][ptr]<=x)ptr++;
                res+=sz(locs[pre])-ptr;
            }
        }
        return res;
    };
    while(q--){
        int a;
        cin>>a;
        tot-=calc(a+1);
        swap(ord[a+1],ord[a]);
        tot+=calc(a+1);
        printf("%lli\n",tot);
    }
    return 0;
}

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