Submission #1102308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102308		adaawf	Swap Swap Sort (CCO21_day1problem1)	C++17	0 / 25	146 ms	23872 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
namespace __gnu_pbds{
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
vector<int> g[100005], v;
int b = 320, dd[100005], a[100005], c[100005];
long long int f[325][100005], d = 0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k, m, z = 0;
    cin >> n >> k >> m;
    ordered_set s;
    for (int i = 1; i <= n; i++) {
        c[i] = i;
        cin >> a[i];
        d += s.order_of_key(a[i]);
        s.insert(a[i]);
        g[a[i]].push_back(i);
    }
    //cout << d << '\n';
    for (int i = 1; i <= k; i++) {
        if (g[i].size() >= b) {
            dd[i] = ++z;
        }
    }
    for (int i = 1; i <= k; i++) {
        if (dd[i] == 0) continue;
        int c = g[i].size(), h = 1;
        for (int w : g[i]) {
            for (int j = h; j < w; j++) {
                f[dd[i]][a[j]] += c;
            }
            h = w + 1;
            c--;
        }
    }
    for (int i = 1; i <= m; i++) {
        long long int x, y, h, flag = 0, res = 0;
        cin >> x;
        h = x;
        y = x + 1;
        x = c[x]; y = c[y];
        if (g[x].size() > g[y].size()) {
            swap(x, y);
            flag = 1;
        }
        if (g[y].size() < b) {
            int l = 0;
            for (int w : g[y]) {
                while (l < g[x].size() && g[x][l] < w) {
                    l++;
                }
                res += l;
            }
        }
        else res = f[dd[y]][x];
        if (flag == 1) {
            res = 1ll * g[x].size() * g[y].size() - res;
        }
        d += res * 2 - 1ll * g[x].size() * g[y].size();
        swap(c[h], c[h + 1]);
        cout << d << '\n';
        //cout << d << " " << res << " " << g[x].size() << " " << g[y].size() << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         if (g[i].size() >= b) {
      |             ~~~~~~~~~~~~^~~~
Main.cpp:54:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         if (g[y].size() < b) {
      |             ~~~~~~~~~~~~^~~
Main.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 while (l < g[x].size() && g[x][l] < w) {
      |                        ~~^~~~~~~~~~~~~

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