Submission #1248228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248228		noob123	Swap Swap Sort (CCO21_day1problem1)	C++20	6 / 25	5095 ms	6724 KiB

Main

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

struct Fenwick {
    int n;
    vector<ll> f;
    Fenwick(int _n): n(_n), f(n+1,0) {}
    void update(int i, ll v=1){
        for(; i<=n; i+=i&-i) f[i] += v;
    }
    ll query(int i){
        ll s=0;
        for(; i>0; i-=i&-i) s += f[i];
        return s;
    }
    ll query(int l, int r){
        if(l>r) return 0;
        return query(r) - query(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    long q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }

    vector<vector<int>> pos(k+1);
    for(int i=0;i<n;i++){
        pos[a[i]].push_back(i);
    }

    Fenwick fw(k);
    ll inv = 0;
    for(int i=0;i<n;i++){
        inv += fw.query(a[i]+1, k);
        fw.update(a[i], 1);
    }

    vector<int> p(k+1), r(k+1);
    for(int i=1;i<=k;i++){
        p[i] = i;
        r[i] = i;
    }

    while(q--){
        int j;
        cin >> j;             
        int x = p[j], y = p[j+1];
        ll Cxy = 0, Cyx = 0;
        auto &vx = pos[x];
        auto &vy = pos[y];
        if(vx.size() < vy.size()){
            for(int idx: vx){
                Cxy += (ll)(vy.end() - upper_bound(vy.begin(), vy.end(), idx));
            }
            for(int idx: vy){
                Cyx += (ll)(vx.end() - upper_bound(vx.begin(), vx.end(), idx));
            }
        } else {
            for(int idx: vy){
                Cyx += (ll)(vx.end() - upper_bound(vx.begin(), vx.end(), idx));
            }
            for(int idx: vx){
                Cxy += (ll)(vy.end() - upper_bound(vy.begin(), vy.end(), idx));
            }
        }

        inv += Cxy - Cyx;
        swap(p[j], p[j+1]);
        r[x] = j+1; 
        r[y] = j;

        cout << inv << "\n";
    }

    return 0;
}

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