Submission #795878

#	Time	Username	Problem	Language	Result	Execution time	Memory
795878		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	145 ms	140096 KiB

shoes

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

using namespace std;

const int tam = 200010;
int bit[tam];
void add(int pos, int val)
{
	while(pos < tam)
		bit[pos] += val, pos += pos & -pos;
}
int query(int pos)
{
	int res = 0;
	while(pos)
		res += bit[pos], pos -= pos & -pos;
	return res;
}

long long count_swaps(std::vector<int> s) {
	int n = (int)s.size() / 2;
	// cout<<n<<'\n';
	vector<queue<int>> colasp(n + 1), colasn(n + 1);
	vector<pair<int, int>> pares;
	// cout<<s.size()<<'\n';
	for(int i = 0; i < 2 * n; i++)
	{
		// cout<<i<<'\n';
		add(i + 1, 1);
		if(s[i] > 0)
		{
			if(colasn[s[i]].empty())
				colasp[s[i]].push(i);
			else
				pares.push_back({colasn[s[i]].front(), i}), colasn[s[i]].pop();
		}
		else
		{
			if(colasp[-s[i]].empty())
				colasn[-s[i]].push(i);
			else
				pares.push_back({colasp[-s[i]].front(), i}), colasp[-s[i]].pop();
		}
	}
	long long res = 0;
	sort(pares.begin(), pares.end());
	// cout<<pares.size()<<'\n';
	for(int i = 0; i < n; i++)
	{
		// cout<<i<<'\n';
		int a = pares[i].first, b = pares[i].second;
		res += query(b) - query(a + 1);
		if(s[a] > 0)
			res++;
		add(b + 1, -1);
		add(a + 1, 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