Submission #785193

#	Time	Username	Problem	Language	Result	Execution time	Memory
785193		acatmeowmeow	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	313 ms	22712 KiB

shoes

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

using namespace std;

const int N = 1e5;
int tree[2*N + 5];
set<pair<int, int>> f, se;

void update(int n, int k, int v) {
	for (; k <= n; k += k&-k) tree[k] += v; 
}

int query(int k) {
	int sum = 0;
	for (; k; k -= k&-k) sum += tree[k];
	return sum;
}

long long count_swaps(std::vector<int> s) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n = s.size()/2;
	s.insert(s.begin(), 0);
	for (int i = 1; i <= 2*n; i++) {
		f.insert({i, s[i]});
		se.insert({s[i], i});
	}
	int index = 1;
   	long long ans = 0;
	while (f.size()) {
		pair<int, int> lef = *f.begin();
		f.erase(f.begin());
		se.erase({lef.second, lef.first});

		pair<int, int> rig = *se.lower_bound({-lef.second, 0});
		se.erase(rig);
		f.erase({rig.second, rig.first});

		if (lef.second > 0) ans++;

		int cur = rig.second + query(2*n) - query(rig.second - 1);
		ans += (long long)cur - index - 1;
		update(2*n, rig.second, 1);

		index += 2;
	}
	return ans;
}

/*signed main() {
	int n;
	cin >> n;
	vector<signed> arr(2*n);
	for (int i = 0; i < 2*n; i++) cin >> arr[i];
	cout << count_swaps(arr) << '\n';
	return 0;
}*/

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