Submission #1022153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022153		induwara16	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1040 ms	21608 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];
	}
}

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

		update(t, v * 2, tl, mid, l, min(r, mid), V);
		update(t, v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, V);
	}
}

int get(vector<int> t, int v, int tl, int tr, int pos)
{
	if (tl == tr)
	{
		return t[v];
	}

	int mid = (tl + tr) / 2;
	if (pos <= mid)
	{
		return t[v] + get(t, v * 2, tl, mid, pos);
	}
	else
	{
		return t[v] + get(t, v * 2 + 1, mid + 1, tr, pos);
	}
}

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();

		if ((ln < 0) && (li == l + 1))
		{
			l += 2;
			continue;
		}

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

		l += 1;

		if (ln > 0 && l == li)
			l += 1;
		else
			update(t, 1, 0, n - 1, li, n - 1, 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