Submission #173656

#	Time	Username	Problem	Language	Result	Execution time	Memory
173656		lckcode	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	190 ms	23832 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int bit[200005], n;
void upd (int x, int v) {
	for (;x <= 2*n; x += x & (-x)) bit[x] += v;
}
int sum (int x) {
	int res = 0;
	for (;x; x-= x & (-x)) res += bit[x];
	return res;
}
#define ll long long
set<int> s[200005];
int a[200005]; bool dead[200005];
long long count_swaps(std::vector<int> S) {
	// cout <<"DUH" << endl;
	ll ans = 0;
	// cout << "DU" << endl;
	n = S.size() / 2;
	// cout << n << endl;
	for (int i = 1; i <= 2*n; ++i) upd(i, 1);
	for (int i = 0; i < 2*n; ++i) a[i+1] = S[i];
	// cout << "yo" << endl;
	for (int i = 1; i <= 2*n; ++i)
		s[a[i]+n].insert(i);
	for (int i = 1; i <= n*2; ++i) {
		if (dead[i]) continue;
		int yo = *s[-a[i]+n].begin();
		s[-a[i]+n].erase(s[-a[i]+n].begin());
		s[a[i]+n].erase(s[a[i]+n].begin());
		ans += sum(yo-1) - sum(i);
		ans += (a[i] > 0);
		upd(i, -1);
		upd(yo, -1); dead[i] = dead[yo] = 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