Submission #983763

#	Time	Username	Problem	Language	Result	Execution time	Memory
983763		arya_nazari_	Swap Swap Sort (CCO21_day1problem1)	C++14	3 / 25	1230 ms	19172 KiB

Main

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

#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
#define pb push_back
#define SZ(x) ((ll)(x).size())

const ll N = 1e5+100, M = 5e3+100;
ll n, k, q, a[N], b[N], target[N];
vector<ll> cnt[N];
map<pii, ll> mp;

ll merge(int l, int mid, int r) {
    ll p1 = l, p2 = mid, pt = l, c = 0;
    while (p1 < mid && p2 < r) {
        //if (l == 2 && r == 5) cout << p1 << " " << p2 << endl;
        if (a[p1] <= a[p2]) {
            b[pt++] = a[p1++];
            c += p2 - mid;
        } else {
            b[pt++] = a[p2++];
            
        }
    }
    //cout << p1 << " " << p2 << endl;


    while (p1 < mid) {
        b[pt++] = a[p1++];
        c += r - mid;
    }

    while (p2 < mid) {
        b[pt++] = a[p2++];
    }

    sort(a+l, a+r);

    return c;
}

ll solve(int l, int r) {
    if (l + 1 == r) return 0;
    int mid = (l + r) / 2;

    ll c = solve(l, mid) + solve(mid, r) + merge(l, mid, r);
    return c;
}

ll count(int ind, int x) {
    int l = 0, r = SZ(cnt[x]) - 1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (ind > cnt[x][mid]) l = mid + 1;
        else r = mid - 1;
    }

    return l;
}

ll calc(int x, int y) {
    ll inv = 0;
    if (SZ(cnt[x]) <= SZ(cnt[y])) {
        for (auto ind: cnt[x]) {
            inv += count(ind, y);
        }
    } else {
        for (auto ind: cnt[y]) {
            //cout << x << " " << y << ": " << ind << " " << inv << endl;
            inv += SZ(cnt[x]) - count(ind, x);
        }
    }

    return inv;
}

int main()
{
    sui
    cin >> n >> k >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
        cnt[a[i]].pb(i);
    }
    for (int i = 1; i <= k; i++) {
        target[i] = i;
    }

    ll total = solve(0, n);

    while (q--) {
        ll j; cin >> j;
        int fi = target[j], se = target[j+1];
        swap(target[j], target[j+1]);
        

        pii cur = {min(target[j], target[j+1]), max(target[j], target[j+1])};

        if (mp.find(cur) == mp.end()) mp[cur] = calc(cur.F, cur.S);
        int inv = mp[cur];

        //cout << cur.F << " " << cur.S << " "<< inv << endl;

        if (fi < se) {
            total += SZ(cnt[fi]) * SZ(cnt[se]) - inv * 2;
        }
        else {
            total += 2 * inv - SZ(cnt[fi]) * SZ(cnt[se]);
        }   
        cout << total << endl;
    }

    //for (int i = 1; i <= k; i++) cout << d[i] << "-" << e[i] << " ";
    return 0;
}

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