Submission #411617

#	Time	Username	Problem	Language	Result	Execution time	Memory
411617		emuyumi	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	1777 ms	251992 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define ms(x,a) memset(x,a,sizeof x)
typedef long long ll;
const int mod=1e9+7, inf=0x3f3f3f3f, MAXN=1e5+1, MAXQ=2e6+1, SZ=5000;

int n, k, q;
int arr[MAXN], tar[MAXN];
int a[MAXQ], b[MAXQ];
ll ans[MAXQ], bad[MAXQ];
int id[MAXN];
set<int> ss;
int cnt[SZ+10];
ll mp[SZ+10][SZ+10];

struct Fenwick{
    int a[MAXN];
    void ins(int i, int v=1){ for (;i<MAXN;i+=i&-i) a[i]+=v; }
    int qry(int i){
        ll ret=0;
        for (;i;i-=i&-i) ret+=a[i];
        return ret;
    }
} bit;

void build(){
    for (int bl=0;bl*SZ<=n;++bl){
        int l=bl*SZ, r=min(n,(bl+1)*SZ-1);
        for (int i=l;i<=r;++i) ss.insert(arr[i]);
        int poi=0;
        for (int x:ss) id[x]=++poi;
        for (int i=l;i<=r;++i){
            arr[i]=id[arr[i]];
            for (int j=1;j<=poi;++j){
                mp[arr[i]][j]+=cnt[j];
            }
            cnt[arr[i]]++;
        }
        // compute answers
        for (int i=1;i<=2*q;++i){
            int aa=id[a[i]];
            int bb=id[b[i]];
            if (aa&&bb) ans[i]+=mp[aa][bb];
            if (aa) ans[i]+=bad[i]*cnt[aa];
            if (bb) bad[i]+=cnt[bb];
        }
        for (int i=1;i<=poi;++i) ms(mp[i],0);
        // resetting
        ss.clear(), ms(id,0);
        ms(cnt,0);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    for (int i=1;i<=n;++i) cin >> arr[i];
    iota(tar+1,tar+1+n,1);
    for (int i=1;i<=q;++i){
        int j; cin >> j;
        a[i*2-1]=tar[j];
        b[i*2-1]=tar[j+1];
        a[i*2]=b[i*2-1];
        b[i*2]=a[i*2-1];
        swap(tar[j],tar[j+1]);
    }
    ll tot=0;
    for (int i=1;i<=n;++i){
        bit.ins(arr[i]);
        tot+=i-bit.qry(arr[i]);
    }
    build();
    for (int i=1;i<=q;++i){
        tot-=ans[i*2-1];
        tot+=ans[i*2];
        // cout << cntinv(a[i],b[i]) << " " << cntinv(b[i],a[i]) << '\n';
        cout << tot << '\n';
    }
}

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