Submission #1290704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290704		kahoul	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	165 ms	110036 KiB

shoes

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

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

const int maxn = 1e5 + 10;
multiset<int> seg[4 * maxn];
int ind[4 * maxn];
int lz[4 * maxn];

vector<int> thing;

void propagate (int idx, int l, int r) {
	if (lz[idx] == 0) return;

	int lazy = lz[idx];
	lz[idx] = 0;

	if (l == r) {
		if (ind[idx] == -1) return;
		ind[idx] += lazy;
		return;
	}

	lz[idx * 2] += lazy;
	lz[idx * 2 + 1] += lazy;
}

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) {
	propagate(idx, l, r);

	if (j < l || r < i) return;
	if (i <= l && r <= j) {
		lz[idx]++;
		propagate(idx, l, r);
		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) {
	propagate(idx, l, r);

	if (i < l || r < i) return;
	if (l == r) {
		seg[idx].erase(thing[i]);
		ind[idx] = -1;
		return;
	}

	int m = (l + r) >> 1;
	remove_elm(idx * 2, l, m, i);
	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) {
	propagate(idx, l, r);

	if (l == r) return ind[idx];

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

pair<int, int> query_find (int idx, int l, int r, int x) {
	propagate(idx, l, r);

	if (l == r) return {ind[idx], l};

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

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);

	for (int i = 1; i <= n; i++) {
		//cout << thing[i] << ' ';
	}
	//cout << '\n';

	for (int i = 1; i <= n; i++) {
		//cout << query_idx(1, 1, n, i) << ' ';
	}
	//cout << '\n';

	int ans = 0;

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

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

		if (idx == -1) 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);
		//cout << nidx << ' ' << idx << ' ' << nreal << '\n';

		int delta = nidx - idx - 1;

		if (v > 0) delta++;

		//cout << delta << '\n';
		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