Submission #464968

#	Time	Username	Problem	Language	Result	Execution time	Memory
464968		JovanB	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	2809 ms	116136 KiB

Main

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

using ll = long long;
using ld = long double;

const int N = 100000;
const int Q = 1000000;

int bit[N+5];

void bit_add(int x){
    while(x <= N) bit[x]++, x += x & -x;
}

int bit_get(int x){
    int res = 0;
    while(x) res += bit[x], x -= x & -x;
    return res;
}

vector <int> vec[N+5];

map <int, int> gde[N+5];
vector <ll> inv[N+5];
int a[N+5], niz[N+5], swp[Q+5];
vector <pair <int, int>> qs[N+5];
int cnt[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, k, qrs;
    cin >> n >> k >> qrs;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        vec[a[i]].push_back(i);
    }
    ll res = 0;
    int added = 0;
    for(int i=1; i<=n; i++){
        for(auto c : vec[i]) res += added - bit_get(c);
        for(auto c : vec[i]) bit_add(c), added++;
    }
    for(int i=1; i<=k; i++) niz[i] = i;
    for(int i=1; i<=k; i++) inv[i].push_back(0);
    for(int i=1; i<=qrs; i++){
        cin >> swp[i];
        int j = swp[i];
        int x = niz[j], y = niz[j+1];
        if(gde[x].count(y) || gde[y].count(x)){
            swap(niz[j], niz[j+1]);
            continue;
        }
        if(vec[x].size() > vec[y].size()) swap(x, y);
        inv[x].push_back(0);
        gde[x][y] = inv[x].size() - 1;
        qs[x].push_back({y, inv[x].size() - 1});
        swap(niz[j], niz[j+1]);
    }
    for(int i=1; i<=n; i++){
        for(auto pr : qs[a[i]]) inv[a[i]][pr.second] += cnt[pr.first];
        cnt[a[i]]++;
    }
    for(int i=1; i<=k; i++) niz[i] = i;
    for(int i=1; i<=qrs; i++){
        int j = swp[i];
        int x = niz[j], y = niz[j+1];
        if(gde[x].count(y)) res += 1LL*vec[x].size()*vec[y].size() - 2*inv[x][gde[x][y]];
        else res += 2*inv[y][gde[y][x]] - 1LL*vec[x].size()*vec[y].size();
        cout << res << "\n";
        swap(niz[j], niz[j+1]);
    }
    return 0;
}

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