Submission #200386

#	Time	Username	Problem	Language	Result	Execution time	Memory
200386		luciocf	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	143 ms	19192 KiB

shoes

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

using namespace std;

typedef long long ll;

const int maxn = 2e5+10;

int a[maxn];

vector<int> pos_esq[maxn], pos_dir[maxn];

int bit[maxn];

void upd(int x, int v)
{
	for (; x < maxn; x += (x&-x))
		bit[x] += v;
}

int soma(int x)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit[x];
	return ans;
}

ll count_swaps(vector<int> s)
{
	int n = (int)s.size();

	for (int i = 1; i <= n; i++)
	{
		a[i] = s[i-1];
		upd(i, 1);
	}

	for (int i = n; i >= 1; i--)
	{
		if (a[i] < 0) pos_esq[-a[i]].push_back(i);
		else pos_dir[a[i]].push_back(i);
	}

	ll ans = 0;

	for (int i = 1; i <= n; i++)
	{
		if (a[i] < 0)
		{
			a[i] = -a[i];

			if (pos_esq[a[i]].back() != i)
				continue;

			int dir = pos_dir[a[i]].back();

			ans += 1ll*(soma(dir)-soma(i)-1);

			pos_esq[a[i]].pop_back(); pos_dir[a[i]].pop_back();

			upd(dir, -1); upd(i, -1);
		}
		else
		{
			if (pos_dir[a[i]].back() != i)
				continue;

			int esq = pos_esq[a[i]].back();

			ans += 1ll*(soma(esq)-soma(i));

			pos_dir[a[i]].pop_back(); pos_esq[a[i]].pop_back();

			upd(i, -1); upd(esq, -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