Submission #1290712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290712		kahoul	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1106 ms	242612 KiB

shoes

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

using namespace std;
typedef pair<int, int> pii;

const int maxn = 2e5 + 10;
unordered_multiset<int> seg[4 * maxn];
int ind[4 * maxn];

vector<int> thing;

void build (int idx, int l, int r) {
	if (l == r) {
		ind[idx] = l;
		seg[idx].insert(thing[l]);
		return;
	}

	int m = (l + r) >> 1;
	build(idx * 2, l, m);
	build(idx * 2 + 1, m + 1, r);
	for (auto v : seg[idx * 2]) {
		seg[idx].insert(v);
	}
	for (auto v : seg[idx * 2 + 1]) {
		seg[idx].insert(v);
	}
}

void update (int idx, int l, int r, int i, int j) {
	if (j < l || r < i) return;
	if (i <= l && r <= j) {
		ind[idx]++;
		return;
	}

	int m = (l + r) >> 1;
	update(idx * 2, l, m, i, j);
	update(idx * 2 + 1, m + 1, r, i, j);
}

void remove_elm (int idx, int l, int r, int i) {
	if (l == r) {
		seg[idx].clear();
		ind[idx] = -1e9;
		return;
	}

	int m = (l + r) >> 1;
	if (i <= m) {
		remove_elm(idx * 2, l, m, i);
	} else {
		remove_elm(idx * 2 + 1, m + 1, r, i);
	}
	seg[idx].erase(seg[idx].find(thing[i]));
}

int query_idx (int idx, int l, int r, int i) {
	if (l == r) return ind[idx];

	int m = (l + r) >> 1;
	if (i <= m)
		return ind[idx] + query_idx(idx * 2, l, m, i);
	else
		return ind[idx] + query_idx(idx * 2 + 1, m + 1, r, i);
}

pair<int, int> query_find (int idx, int l, int r, int x) {
	if (l == r) return {ind[idx], l};

	int m = (l + r) >> 1;
	if (seg[idx * 2].count(x) > 0) {
		auto [index, real] = query_find(idx * 2, l, m, x);
		return {ind[idx] + index, real};
	}
	else {
		auto [index, real] = query_find(idx * 2 + 1, m + 1, r, x);
		return {ind[idx] + index, real};
	}
}

long long count_swaps(vector<int> s) {
	thing.push_back(0);

	int n = s.size();
	deque<pair<int, int>> q;

	for (int i = 1; i <= s.size(); i++) {
		thing.push_back(s[i - 1]);
		q.push_back({s[i - 1], i});
	}

	build(1, 1, n);

	long long ans = 0;

	while (!q.empty()) {
		auto [v, i] = q.front();
		q.pop_front();

		int idx = query_idx(1, 1, n, i);

		if (idx < 0) continue;

		auto [nidx, nreal] = query_find(1, 1, n, -v);

		remove_elm(1, 1, n, i);
		remove_elm(1, 1, n, nreal);
		update(1, 1, n, i, nreal);

		int delta = nidx - idx - 1;
		if (v > 0) delta++;
		ans += delta;
	}

	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