Submission #1102310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102310		vjudge1	Swap Swap Sort (CCO21_day1problem1)	C++17	25 / 25	1549 ms	48668 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;

int B = 100;

vector<int> occ[100008];
int a[100008], p[100008];
vector<long long> f[1008];
int Hrank[100008], pf[100008];

long long res; int pt;
long long query(int x, int y) { // #yx - #xy = -(#x*#y) + 2#yx = #x*#y - 2#xy
	if (occ[x].size() >= B) return -1LL * occ[x].size() * occ[y].size() + 2 * f[Hrank[x]][y];
	if (occ[y].size() >= B) return 1LL * occ[x].size() * occ[y].size() - 2 * f[Hrank[y]][x];
	res = 0; pt = -1;
	for (int o_x : occ[x]) {
		while (pt + 1 < occ[y].size() && occ[y][pt + 1] < o_x) ++pt;
		res -= pt + 1;
	}
	pt = -1;
	for (int o_y : occ[y]) {
		while (pt + 1 < occ[x].size() && occ[x][pt + 1] < o_y) ++pt;
		res += pt + 1;
	}
	return res;
}


struct Binary_Indexed_Tree {
	vector<int> BIT; int n;
	Binary_Indexed_Tree(int n) : n(n) {BIT.assign(n + 8, 0);}
	Binary_Indexed_Tree() {}
	
	int pt, res;
	
	void update(int u) {
	    pt = u;
	    while (pt <= n) {
			++BIT[pt];
			pt += pt & -pt;
	    }
	}
	
	int pf(int p) {
		if (p <= 0) return 0;
	    pt = p; res = 0;
	    while (pt) {
	        res += BIT[pt];
	        pt -= pt & -pt;
	    }
	    return res;
	}
	
	int range(int l, int r) {
		if (l > r) return 0;
		return pf(r) - pf(l - 1);
	}	
};

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k, q, x; cin >> n >> k >> q;
	for (int i = 1; i <= n; ++i) cin >> a[i], occ[a[i]].push_back(i);
	iota(p + 1, p + n + 1, 1); long long inv = 0;
	Binary_Indexed_Tree tree(k);
	for (int i = 1; i <= n; ++i) inv += tree.range(a[i] + 1, k), tree.update(a[i]);
	int m = 0;
	for (x = 1; x <= k; ++x) if (occ[x].size() >= B) {
		++m; Hrank[x] = m;
		for (int i = 1; i <= n; ++i) pf[i] = pf[i - 1] + (a[i] == x);
		f[Hrank[x]].resize(k + 1);
		for (int i = 1; i <= n; ++i) f[Hrank[x]][a[i]] += (a[i] != x ? pf[i] : 0);
	}
	while (q--) {
		cin >> x; swap(p[x], p[x + 1]);
		inv += query(p[x + 1], p[x]); 
		cout << inv << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In function 'long long int query(int, int)':
Main.cpp:15:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |  if (occ[x].size() >= B) return -1LL * occ[x].size() * occ[y].size() + 2 * f[Hrank[x]][y];
      |      ~~~~~~~~~~~~~~^~~~
Main.cpp:16:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |  if (occ[y].size() >= B) return 1LL * occ[x].size() * occ[y].size() - 2 * f[Hrank[y]][x];
      |      ~~~~~~~~~~~~~~^~~~
Main.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   while (pt + 1 < occ[y].size() && occ[y][pt + 1] < o_x) ++pt;
      |          ~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   while (pt + 1 < occ[x].size() && occ[x][pt + 1] < o_y) ++pt;
      |          ~~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:71:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |  for (x = 1; x <= k; ++x) if (occ[x].size() >= B) {
      |                               ~~~~~~~~~~~~~~^~~~

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