Submission #360184

#	Time	Username	Problem	Language	Result	Execution time	Memory
360184		jesus_coconut	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	692 ms	148224 KiB

shoes

#include "shoes.h"
#include <bitset>
#include <map>
#include <deque>
using namespace std;

template<class T>
struct BIT{
	vector<T> bit;

	explicit BIT(int N) : bit(N, 0) {}

	void add(int pos, T val) {
		for (++pos; pos < (int) bit.size(); pos += pos & -pos) {
			bit[pos] += val;
		}
	}

	T sum(int r) {
		T res{};
		for (++r; r > 0; r -= r & -r) {
			res += bit[r];
		}
		return res;
	}

	T sum(int l, int r) { return sum(r) - sum(l - 1); }
};


long long count_swaps(std::vector<int> s) {
	int n = s.size();
	BIT<int> bit(n + 1);
	map<int, deque<int>> mp;
	for (int i = 0; i < n; ++i) {
		mp[s[i]].push_back(i);
	}
	using ll = long long;
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		if (bit.sum(i, i)) continue;
		int r = mp[-s[i]].front();
		ans += r - i - bit.sum(i, r) - (s[i] < 0);
		bit.add(r, 1);
		mp[-s[i]].pop_front();
		mp[s[i]].pop_front();
	}
	return ans;
}

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