제출 #528767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528767		ahmeteren	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	301 ms	32952 KiB

shoes

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

#define ll long long
const int N = 2e5 + 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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15