Submission #1258985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258985		healme	Swap Swap Sort (CCO21_day1problem1)	C++20	25 / 25	2142 ms	84228 KiB

Main

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

#define F first
#define S second
#define all(a) a.begin(), a.end()
#define pb push_back
#define int long long
typedef long long ll;
typedef pair<int, int> ii;

void print() { cerr << '\n'; }
template<typename T1, typename... T2>
void print(T1 a, T2... b) { cerr << a << ' '; print(b...); }

const int N = 2e5 + 5;
int n, k, q, id[N], a[N];
int bit[N];
vector<int> pos[N];
int res = 0;

void upd(int u, int val)
{
    for (; u > 0; u -= u & (-u)) bit[u] += val;
}

int get(int u)
{
    int res = 0;
    for (; u < N; u += u & (-u)) res += bit[u];
    return res;
}

map<ii, int> mp;
int calc(int u, int v)
{
    if(mp.count({u, v}))
        return mp[{u, v}];

    int &res = mp[{u, v}];
    if(pos[u].size() < pos[v].size())
    {
        for(const int &x : pos[u])
            res += lower_bound(all(pos[v]), x) - pos[v].begin();
    }
    else
    {
        for(const int &x : pos[v])
            res += pos[u].end() - upper_bound(all(pos[u]), x);
    }
    return res;
}

void solve()
{
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pos[a[i]].pb(i);
    }
    for(int i = 1; i <= k; i++)
        id[i] = i;
    for(int i = 1; i <= n; i++)
    {
        res += get(a[i] + 1);
        upd(a[i], 1);
    }

    while(q--)
    {
        int j;
        cin >> j;
        res += pos[id[j]].size() * pos[id[j + 1]].size() - 2 * calc(id[j], id[j + 1]);
        cout << res << '\n';
        swap(id[j], id[j + 1]);
    }
}

signed main()
{
    if(fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

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

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