Submission #1043836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043836		fv3	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	173 ms	276048 KiB

shoes

// 65 points

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

using namespace std;
typedef long long ll;

int nt = 1;
vector<int> st;

int get_range(int l, int r, int k, int x, int y)
{
	if (x > r || y < l) return 0;
	if (x >= l && y <= r) return st[k];
	int c = (x + y) / 2;
	return get_range(l, r, k*2, x, c) + get_range(l, r, k*2|1, c+1, y);
}

ll count_swaps(vector<int> s) 
{
	// 1. Find pairs
	// 2. Use segment tree to keep track of offsets
	// 3. Profit

	const ll N = s.size() / 2;
	vector<queue<int>> vq(4 * N + 2);

	// Finding mathcing shoes:)
	vector<int> match(2 * N);
	for (int i = 0; i < 2 * N; i++)
	{
		if (vq[2 * N + 1 - s[i]].size())
		{
			int matchIndex = vq[2 * N + 1 - s[i]].front();
			match[i] = matchIndex;
			match[matchIndex] = i;
			vq[2 * N + 1 - s[i]].pop();
		}
		else
		{
			vq[2 * N + 1 + s[i]].push(i);
		}
	}

	// Offset segment tree:)
	while (nt < 2 * N)
		nt <<= 1;
	st = vector<int>(2*nt);

	// Profit B)
	ll res = 0;

	int l = 0, r = 2*N - 1;
	while (l < r)
	{
		while (match[l] == -1)
		{
			if (++l >= r)
				return res;
		}
		int leftMatch = match[l];

		int offset_l = get_range(0, l, 1, 0, nt - 1);
		int offset_match = get_range(0, leftMatch, 1, 0, nt - 1);

		int range = leftMatch + offset_match - (l + offset_l); 
		if (s[l] < 0) range--;

		res += range;
		match[l] = -1; match[leftMatch] = -1;

		{
			int i = nt + l;
			st[i]++;
			for (i /= 2; i >= 1; i /= 2)
				st[i] = st[i * 2] + st[i * 2 | 1];
		}

		{
			int i = nt + leftMatch;
			st[i]--;
			for (i /= 2; i >= 1; i /= 2)
				st[i] = st[i * 2] + st[i * 2 | 1];
		}
	}

	return res;
}

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