Submission #1102268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102268		Thanhs	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	2391 ms	98376 KiB

Main

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

#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e5 + 5;
const int SQ = 320;

vector<int> p[NM], B;
int n, k, q, cost[2][SQ + 5][NM], cnt[SQ + 5], big[NM], bit[NM], cur, a[NM], P[NM];

void upd(int i)
{
    for (; i <= n; i += i & -i)
        bit[i]++;
}

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

void Swap(int x, int y)
{
    if (!big[x] && !big[y])
    {
        int j = 0;
        for (int i = 0; i < p[x].size(); i++)
        {
            while (j < p[y].size() && p[y][j] < p[x][i])
                j++;
            cur -= j;
            cur += p[y].size() - j;
        }
    }
    else if (big[x])
        cur += cost[0][big[x]][y] - cost[1][big[x]][y];
    else
        cur += cost[1][big[y]][x] - cost[0][big[y]][x];
}

void solve()
{
    cin >> n >> k >> q;
    iota(P + 1, P + 1 + k, 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        p[a[i]].push_back(i);
    }
    B.push_back(0);
    for (int i = 1; i <= k; i++)
        if (p[i].size() >= SQ)
        {
            big[i] = B.size();
            B.push_back(i);
        }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < B.size(); j++)
        {
            cost[0][j][a[i]] += cnt[j];
            cost[1][j][a[i]] += p[B[j]].size() - cnt[j];
        }
        if (big[a[i]])
            cnt[big[a[i]]]++;
    }
    cur = 0;
    for (int i = n; i >= 1; i--)
    {
        cur += get(a[i] - 1);
        upd(a[i]);
    }
    while (q--)
    {
        int x;
        cin >> x;
        Swap(P[x], P[x + 1]);
        swap(P[x], P[x + 1]);
        cout << cur << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'void Swap(long long int, long long int)':
Main.cpp:40:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < p[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while (j < p[y].size() && p[y][j] < p[x][i])
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:72:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 1; j < B.size(); j++)
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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