Submission #244429

#	Time	Username	Problem	Language	Result	Execution time	Memory
244429		tictaccat	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	106 ms	15864 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

struct ft {
	int N; vector<int> tr;
	ft(int N): N(N), tr(N+1,0) {}
	int sum(int i) {
		i++;
		int ans = 0;
		while (i > 0) {
			ans += tr[i];
			i -= i&-i;
		}
		return ans;
	}
	int sumR(int i, int j) {
		return sum(j) - sum(i);
	}
	void add(int i, int x) {
		i++;
		while (i <= N) {
			tr[i] += x;
			i += i&-i;
		}
	}
};

long long count_swaps(std::vector<int> s) {

	int n = s.size() / 2;

	vector<vector<int>> posL(n+1), posR(n+1);
	vector<int> R(2*n, -1);

	for (int i = 0; i < 2*n; i++) {
		if (s[i] > 0) posR[s[i]].push_back(i);
		else posL[-s[i]].push_back(i);
	}

	long long ans = 0;

	for (int j = 1; j <= n; j++) {
		for (int k = 0; k < (int)posR[j].size(); k++) {
		//	cout << posL[j][k] << " " << posR[j][k] << "\n";
			//ans += abs(posR[j][k] - posL[j][k]) - 1;
			if (posR[j][k] < posL[j][k]) {
				R[posR[j][k]] = posL[j][k];
				ans++;
			}
			else R[posL[j][k]] = posR[j][k];
		}
	}

	ft tree(2*n);

	for (int i = 0; i < 2*n; i++) {
		if (R[i] == -1) continue;
	//	cout << i << " " << R[i] << " " << tree.sum(1) << "\n";
		ans += R[i] - i - 1 - tree.sumR(i,R[i]);
		tree.add(R[i],1);
	}

	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15