Submission #1021880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021880		induwara16	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	348 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;
#define itr(a) a.begin(), a.end()

typedef vector<int> vi;
typedef unordered_map<int, int> mii;

void build(vector<int> &t, vector<int> arr, int v, int l, int r)
{
	if (l == r)
	{
		t[l] = 0;
	}
	else
	{
		int mid = (l + r) / 2;
		build(t, arr, v * 2, l, mid);
		build(t, arr, v * 2 + 1, mid + 1, r);

		t[v] = t[v * 2] + t[v * 2 + 1];
	}
}

int sum(vector<int> t, int v, int tl, int tr, int l, int r)
{
	if (l > r)
		return 0;
	if (tl == l && tr == r)
		return t[v];

	int mid = (tl + tr) / 2;
	return sum(t, v * 2, tl, mid, l, min(r, mid)) + sum(t, v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}

void update(vector<int> &t, int v, int l, int r, int i, int V)
{
	if (l == r)
	{
		t[i] += V;
	}
	else
	{
		int mid = (l + r) / 2;

		if (i <= mid)
			update(t, v * 2, l, mid, i, V);
		else
			update(t, v * 2 + 1, mid + 1, r, i, V);

		t[v] = t[v * 2] + t[v * 2 + 1];
	}
}

long long count_swaps(vi s)
{
	int n = s.size(), l = 0;
	long long c = 0;

	mii chain, rev;
	vector<int> t(n * 4);

	unordered_map<int, queue<int>> ref;

	build(t, s, 1, 0, n - 1);

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

	for (int i = 0; i < n / 2; i++)
	{
		int ln = s[l], li = l;

		li = ref[-ln].front();
		ref[ln].pop();
		ref[-ln].pop();

		c += li - l - sum(t, 1, 0, n - 1, l, li) - (ln < 0);
		update(t, 1, 0, n - 1, li, 1);

		if (l + 1 == li)
			l += 2;
		else
			l += 1;
	}

	return c;
}

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