Submission #589423

#	Time	Username	Problem	Language	Result	Execution time	Memory
589423		Soumya1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	129 ms	20932 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
int t[4 * mxN];
void update(int x, int lx, int rx, int i, int v) {
	if (lx == rx) {
		t[x] = v;
		return;
	}
	int mx = (lx + rx) >> 1;
	if (i <= mx) update(x << 1, lx, mx, i, v);
	else update(x << 1 | 1, mx + 1, rx, i, v);
	t[x] = t[x << 1] + t[x << 1 | 1];
}
int query(int x, int lx, int rx, int l, int r) {
	if (l > r) return 0;
	if (l > rx || lx > r) return 0;
	if (l <= lx && r >= rx) return t[x];
	int mx = (lx + rx) >> 1;
	return query(x << 1, lx, mx, l, r) + query(x << 1 | 1, mx + 1, rx, l, r);
}
long long count_swaps(vector<int> s) {
	int n = s.size();
	long long ans = 0;
	vector<int> a[n][2];
	vector<bool> taken(n);
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] < 0) a[-s[i]][0].push_back(i);
		else a[s[i]][1].push_back(i);
	}
	for (int i = 1; i <= n; i++) update(1, 1, n, i, 1);
	for (int i = 0; i < n; i++) {
		if (taken[i]) continue;
		int si = abs(s[i]);
		int other = (s[i] < 0 ? a[si][1].back() : a[si][0].back());
		ans += query(1, 1, n, i + 2, other);
		update(1, 1, n, other + 1, 0);
		if (s[i] > 0) ans++;
		taken[other] = true;
		a[si][0].pop_back();
		a[si][1].pop_back();
	}
	return ans;
}

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