Submission #528765

#	Time	Username	Problem	Language	Result	Execution time	Memory
528765		ahmeteren	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	149 ms	63640 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e5 + 5;

ll bit[N];

void update(int ind, int val)
{
	for(; ind < N; ind = (ind | (ind + 1)))
		bit[ind] += val;
}

ll query(int ind)
{
	ll res = 0;

	for(; ind >= 0; ind = (ind & (ind + 1)) - 1)
		res += bit[ind];

	return res;
}

long long count_swaps(std::vector<int> s)
{
	int n = s.size();
	map<int, set<int>> mp;
	vector<bool> vec(n);

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

	for(int i = 0; i < n; i++)
		update(i, 1);

	ll ans = 0;

	for(int i = 0; i < n; i++)
	{
		if(vec[i])
			continue;
		ans += (s[i] > 0);

		auto it = mp[-s[i]].lower_bound(i);
		int j = *it;
		mp[-s[i]].erase(it);

		vec[i] = vec[j] = true;
		update(i, -1);
		update(j, -1);

		ans += query(j) - query(i);
	}

	return ans;
}

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