Submission #169552

#	Time	Username	Problem	Language	Result	Execution time	Memory
169552		BessieTheCow	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	286 ms	13328 KiB

shoes

#include "shoes.h"
#include <map>
#include <cmath>
#include <utility>

using namespace std;

constexpr int maxn = 200005;

int n;

//Binary indexed tree aka Fenwick tree template
//Increment indices for 0 indexing, querying index 0 gives 0
//Do not update index 0
//Copy y when doing 2D

int bit[maxn];

void update(int index, int val)
{
	index++;
	for (; index <= n; index += index & -index)
	{
		bit[index] += val;
	}
}

int query(int index)
{
	index++;
	int sum = 0;
	for (; index > 0; index -= index & -index)
	{
		sum += bit[index];
	}
	return sum;
}

//End of template

int cnt[2 * maxn];
int c[maxn];
int id[maxn];
bool leftencountered[maxn];
bool removed[maxn];
int rightindex[maxn];

long long count_swaps(vector<int> s)
{
	n = s.size();
	map<pair<int, int>, int> comp;
	for (int i = 0; i < n; i++)
	{
		c[i] = cnt[s[i] + 100000]++;
		comp[{abs(s[i]), c[i]}];
	}
	int cnt = 0;
	for (auto& v : comp)
	{
		v.second = cnt++;
	}
	for (int i = 0; i < n; i++)
	{
		id[i] = comp[{abs(s[i]), c[i]}];
	}
	long long total = 0;
	for (int i = 0; i < n; i++)
	{
		if (s[i] < 0)
		{
			leftencountered[id[i]] = true;
		}
		else if (!leftencountered[id[i]])
		{
			total++;
		}
	}
	for (int i = 0; i < n; i++)
	{
		rightindex[id[i]] = i;
	}
	int prevremoved = 0;
	for (int i = 0; i < n; i++)
	{
		if (removed[i])
		{
			prevremoved++;
			continue;
		}
		int right = rightindex[id[i]];
		total += right - i - 1 - (query(right - 1) - prevremoved);
		removed[right] = true;
		update(right, 1);
	}
	return total;
}

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