Submission #1256424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256424		haru09	Swap Swap Sort (CCO21_day1problem1)	C++20	25 / 25	1341 ms	46084 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "code"

const int ar = 1e5 + 5;
const ll mod = 1e9 + 7;
const int block = 100;
int n, k, q;
int a[ar];
int f[ar];
int mp[ar];
ll cost[ar / block + 1][ar];
vector<int> lis[ar];
int bit[ar];
ll ans = 0;
void update(int u, int v)
{
    while(u <= n)
    {
        bit[u] += v;
        u += u & (-u);
    }
}
int get(int u)
{
    int ans = 0;
    while(u > 0)
    {
        ans += bit[u];
        u -= u & (-u);
    }
    return ans;
}
void build()
{
    for (int i = k; i >= 1; i--)
    {
        for (int u : lis[i]) ans += get(u);
        for (int u : lis[i]) update(u, 1);
    }
}
ll calc_inversion(int u, int v)
{
    ll ans = 0;
    int i = 0, j = 0;
    while(i < lis[u].size() && j < lis[v].size())
    {
        if (lis[u][i] < lis[v][j])
        {
            i++;
            ans += j;
        }
        else j++;
    }
    while(i < lis[u].size())
    {
        i++;
        ans += j;
    }
    return ans;
}
ll calc(int u, int v)
{
    if (lis[u].size() >= block) return 1ll * lis[u].size() * lis[v].size() - cost[mp[u]][v];
    if (lis[v].size() >= block) return cost[mp[v]][u];
    return calc_inversion(u, v);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) cin >> a[i], lis[a[i]].push_back(i);
    for (int i = 1; i <= k; i++) f[i] = i;
    int dem = 0;
    for (int u = 1; u <= k; u++)
    {
        if (lis[u].size() < block) continue;
        int cnt = 0;
        mp[u] = ++dem;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] == u) cnt++;
            else cost[mp[u]][a[i]] += cnt;
        }
    }
    build();
    while(q--)
    {
        int j;
        cin >> j;
        ans -= calc(f[j], f[j + 1]);
        swap(f[j], f[j + 1]);
        ans += calc(f[j], f[j + 1]);
        cout << ans << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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