Submission #995076

#	Time	Username	Problem	Language	Result	Execution time	Memory
995076		vyshniak_n	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	2698 ms	507216 KiB

Main

#pragma optimize("Ofast")
#pragma optimize("unroll-loops")
#pragma traget("avx,avx2")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

#include <random>
mt19937 rnd(time(0));

const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll LOG = 20;

const int K = 1e3 + 20;
const int SZ = 1e2 + 20;
int a[N], id[SZ][N], diff[SZ], dp[SZ][K][K], every[SZ][N];

// fenwick tree
struct fenwick_tree {
    vector <ll> fen;
    int sz;

    fenwick_tree(int n) {
        sz = n;
        fen.resize(sz + 1);
    }

    void upd(int v, ll val) {
        for (; v <= sz; v = (v | (v + 1)))
            fen[v] += val;
    }
    ll get(int v) {
        ll res = 0;
        for (; v >= 0; v = (v & (v + 1)) - 1)
            res += fen[v];
        return res;
    }
};

void solve() {
    int n, k, q;
    cin >> n >> k >> q;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector <int> p(k + 1);
    for (ll i = 1; i <= k; i++)
        p[i] = i;

    // calc for every block
    int sz = (n + K - 1) / K;
    for (int i = 0; i < sz; i++)
        for (int j = 0; j < N; j++)
            id[i][j] = -1;
    for (int i = 0; i < n; i++) {
        if (id[i / K][a[i]] == -1)
            id[i / K][a[i]] = diff[i / K]++;
        every[i / K][a[i]]++;
    }

    for (int i = 0; i < sz; i++) {
        for (int f = 0; f < diff[i]; f++) {
            int l = i * K, r = min((i + 1) * K - 1, n - 1);

            int cnt[K];
            for (int j = 0; j < K; j++)
                cnt[j] = 0;

            int cur = 0;
            for (int j = r; j >= l; j--) {
                if (id[i][a[j]] == f) cur++;
                else cnt[id[i][a[j]]] += cur;
            }

            for (int j = 0; j < K; j++)
                dp[i][f][j] = cnt[j];
        }
    }

    // count the number of operation for permutation like {1, 2, 3, ...}
    fenwick_tree used(n), ans(k);
    vector <int> pos[k + 1];

    for (int i = 0; i < n; i++)
        pos[a[i]].pb(i);

    ll already = 0;
    for (int i = 1; i <= k; i++) {
        ll cur = 0;
        for (int x : pos[i]) {
            cur += x + used.get(n - 1) - used.get(x) - already;
            already++;
            used.upd(x, 1);
        }

        ans.upd(i, cur);
    }

    // queries

    while (q--) {
        int x;
        cin >> x;

        ll l = ans.get(x) - ans.get(x - 1);
        ll r = ans.get(x + 1) - ans.get(x);

        ans.upd(x, -l);
        ans.upd(x + 1, -r); 

        ll cur, suff;

        cur = 0, suff = 0;
        for (int i = sz - 1; i >= 0; i--) {
            cur += every[i][p[x + 1]] * 1ll * suff;
            suff += (ll)every[i][p[x]];

            if (id[i][p[x]] == -1 || id[i][p[x + 1]] == -1)
                continue;
            cur += dp[i][id[i][p[x]]][id[i][p[x + 1]]];
        }

        r -= cur;

        swap(p[x], p[x + 1]);

        cur = 0, suff = 0;
        for (int i = sz - 1; i >= 0; i--) {
            cur += every[i][p[x + 1]] * 1ll * suff;
            suff += (ll)every[i][p[x]];

            if (id[i][p[x]] == -1 || id[i][p[x + 1]] == -1)
                continue;
            cur += dp[i][id[i][p[x]]][id[i][p[x + 1]]];
        }

        l += cur;

        ans.upd(x, r);
        ans.upd(x + 1, l); 

        cout << ans.get(k) << el;
    }
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--) 
        solve();
    return 0;
}
/*
*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Ofast")
      | 
Main.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("unroll-loops")
      | 
Main.cpp:3: warning: ignoring '#pragma traget ' [-Wunknown-pragmas]
    3 | #pragma traget("avx,avx2")
      |

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