Submission #1150607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150607		eldorbek_008	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	346 ms	29252 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

long long count_swaps(std::vector<int> a) {
	int n = a.size();
	map<int, vector<int>> pos;
	for (int i = 0; i < n; i++) {
		pos[a[i]].push_back(i);
	}
	vector<int> best(n, -1);
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] == 0 or pos[-a[i]].size() == 0) {
			continue;
		}
		best[i] = pos[-a[i]].back();
		a[best[i]] = 0;
		pos[-a[i]].pop_back();
		pos[a[i]].pop_back();
	}
	int sz = 0;
	int ans = 0;
	ordered_set st;
	for (int i = n - 1; i >= 0; i--) {
		if (best[i] == -1) continue;
		while (st.size() and *st.find_by_order(st.size() - 1) >= i) {
			st.erase(st.find_by_order(st.size() - 1));
		}
		int cur = i - best[i];
		if (st.size() != 0) {
			int j = -1;
			int l = 0, r = st.size() - 1;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (*st.find_by_order(mid) <= best[i]) {
					l = mid + 1;
				} else {
					j = mid;
					r = mid - 1;
				}
			}
			if (j != -1) cur -= st.size() - j;
		}
		ans += cur;
		if (a[i] > 0) {
			ans -= 1;
		}
		st.insert(best[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