Submission #839155

#	Time	Username	Problem	Language	Result	Execution time	Memory
839155		DarkMatter	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	354 ms	29156 KiB

shoes

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

using namespace std;
typedef long long ll;
vector<ll>seg;
void update(int i, int v, int x, int lx, int rx) {
	if (lx + 1 == rx) {
		seg[x] += v;
		return;
	}
	int mid = (lx + rx) / 2;
	if (i < mid)
		update(i, v, 2 * x + 1, lx, mid);
	else
		update(i, v, 2 * x + 2, mid, rx);
	seg[x] = seg[2 * x + 1] + seg[2 * x + 2];
}
ll get(int l, int r, int x, int lx, int rx) {
	if (lx >= r || rx <= l)
		return 0;
	if (lx >= l && rx <= r)
		return seg[x];
	int mid = (lx + rx) / 2;
	return (get(l, r, 2 * x + 1, lx, mid) + get(l, r, 2 * x + 2, mid, rx));
}
long long count_swaps(std::vector<int> v) {
	int n = v.size();
	ll ans = 0;
	int siz = 1;
	while (siz < n)
		siz *= 2;
	seg.resize(2 * siz, 0LL);
	map<int, priority_queue<int, vector<int>, greater<int>>>idx;
	for (int i = 0; i < n; i++)
		idx[v[i]].push(i);
	vector<bool>vis(n + 1, false);
	for (int i = 0; i < n; i++) {
		if (vis[i])
			continue;
		int j = idx[-v[i]].top();
		vis[i] = vis[j] = true;
		idx[v[i]].pop(), idx[-v[i]].pop();
		ll valJ = j + get(0, j + 1, 0, 0, siz), valI = i + get(0, i + 1, 0, 0, siz);
		ll dif = valJ - valI - 1;
		if (valI % 2 == 0 && v[i] < 0)
			ans += dif;
		else
			ans += dif + 1;
		update(i + 1, 1, 0, 0, siz);
		update(j + 1, -1, 0, 0, siz);
	}
	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