제출 #839154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839154		DarkMatter	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	402 ms	1048576 KiB

shoes

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

using namespace std;
typedef long long ll;
vector<ll>seg;
void update(int i, ll v, int x, int lx, int rx) {
	if (lx + 1 == rx) {
		seg[i] = v;
		return;
	}
	int mid = (lx + rx) / 2, idx1 = 2 * x + 1, idx2 = 2 * x + 2;
	if (i < mid)
		update(i, v, idx1, lx, mid);
	else
		update(i, v, idx2, mid, rx);
	seg[x] = seg[idx1] + seg[idx2];
}
ll get(int l, int r, int x, int lx, int rx) {
	if (lx >= r || rx <= l)
		return 0;
	if (lx >= l && rx <= r)
		return seg[x];
	int mid = (lx + rx), idx1 = 2 * x + 1, idx2 = 2 * x + 2;
	return (get(l, r, idx1, lx, mid) + get(l, r, idx2, mid, rx));
}
long long count_swaps(std::vector<int> v) {
	int n = v.size();
	ll ans = 0;
	int siz = 1;
	while (siz < n)
		siz *= 2;
	seg.resize(2 * siz, 0);
	for (int i = 0; i < n; i++)
		update(i, i, 0, 0, siz);
	map<int, priority_queue<int>>idx;
	for (int i = 0; i < n; i++)
		idx[v[i]].push(i);
	vector<bool>vis(n + 1, false);
	for (int i = 0; i < n; i++) {
		if (vis[i])
			continue;
		int j = idx[-v[i]].top();
		vis[i] = vis[j] = true;
		idx[-v[i]].pop();
		ll valJ = get(0, j + 1, 0, 0, siz), valI = get(0, i + 1, 0, 0, siz);
		ll dif = valJ - valI;
		if (valI % 2 == 0 && v[i] < 0)
			ans += dif;
		else
			ans += dif + 1;
		update(i + 1, 1, 0, 0, siz);
		update(j + 1, -1, 0, 0, siz);
	}
	return ans;
}

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