Submission #1275347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275347		rafsanamin2020	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	399 ms	152324 KiB

shoes

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

using namespace std;

const int MX = 4E5;

vector<bool> paired(MX, false);
map<int, queue<int>> nxt;

vector<int> tree(4 * MX, 0);

void update(int l, int r, int x = 0, int lo = 0, int hi = MX - 1)
{
	if (r < lo || l > hi || r < l)
		return;

	// cout << l << " " << r << " " << tree[x] << " \n";
	if ((lo == l && hi == r))
	{
		tree[x]++;

		return;
	}

	int mid = (lo + hi) / 2;

	update(l, min(mid, r), 2 * x + 1, lo, mid);
	update(max(l, mid + 1), r, 2 * x + 2, mid + 1, hi);
}

int query(int t, int x = 0, int lo = 0, int hi = MX - 1)
{
	if (t < lo || t > hi)
		return 0;

	if (lo == hi && lo == t)
	{
		return tree[x];
	}

	int mid = (lo + hi) / 2;

	return query(t, 2 * x + 1, lo, mid) + query(t, 2 * x + 2, mid + 1, hi) + tree[x];
}

long long count_swaps(std::vector<int> s)
{
	long long N = s.size(), ans = 0;

	for (int i = 0; i < N; i++)
	{
		nxt[s[i]].push(i);
	}

	for (int i = 0; i < N; i++)
	{
		if (paired[i])
			continue;

		int j = nxt[-s[i]].front();
		nxt[-s[i]].pop();
		nxt[s[i]].pop();

		update(i + 1, j - 1);

		// cout << i << " " << query(i) << " " << j << " " << query(j) << " " << s[i] << " " << s[j] << " " << ans << "\n";

		ans += (j + query(j)) - (i + query(i)) - (s[i] < 0 ? 1 : 0);

		paired[j] = true;
	}

	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