제출 #1102317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102317		vjudge1	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	3031 ms	129892 KiB

Main

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

#define ll long long
#define pii pair <int, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, QM = 1e6;

int N, K, Q, a[NM+5], bit[NM+5], p[NM+5], cnt[NM+5];
int f[QM+5], g[QM+5];
ll res[QM+5];
vector <pil> queries[NM+5];
map <pii, ll> inv_cnt;

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

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> Q;
    for (int i = 1; i <= N; i++){
        cin >> a[i];
        p[i] = i;
        cnt[a[i]]++;
    }
    for (int i = N; i >= 1; i--){
        res[0] += get(a[i]-1);
        update(a[i]);
    }
    for (int i = 1; i <= Q; i++){
        int x; cin >> x;
        f[i] = p[x], g[i] = p[x+1];
        swap(p[x], p[x+1]);
        int u = f[i], v = g[i];
        if (cnt[u] > cnt[v] || (cnt[u] == cnt[v] && u > v)) swap(u, v);
        if (!inv_cnt.count(mp(u, v))){
            queries[u].push_back(mp(v, 0LL));
            inv_cnt[mp(u, v)] = 0;
        }
    }
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= N; i++){
        for (pil &t : queries[a[i]])
            t.se += cnt[t.fi];
        cnt[a[i]]++;
    }
    for (int i = 1; i <= N; i++)
        for (pil t : queries[i]) inv_cnt[mp(i, t.fi)] = t.se;

    for (int i = 1; i <= Q; i++){
        if (inv_cnt.count(mp(f[i], g[i]))) res[i] = res[i-1]+1LL*cnt[f[i]]*cnt[g[i]]-2*inv_cnt[mp(f[i], g[i])];
        else res[i] = res[i-1]+2*inv_cnt[mp(g[i], f[i])]-1LL*cnt[f[i]]*cnt[g[i]];
        cout << res[i] << '\n';
    }
    return 0;
}

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