Submission #379626

#	Time	Username	Problem	Language	Result	Execution time	Memory
379626		SuhaibSawalha1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	129 ms	19652 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> fen;
int n;

void update (int i, int x) {
	for (++i; i <= n; i += i&-i) {
		fen[i] += x;
	}
}

int query (int i) {
	int ans = 0;
	for (++i; i; i -= i&-i) {
		ans += fen[i];
	}
	return ans;
}

int query (int i, int j) {
	return query(j) - query(i - 1);
}

long long count_swaps(vector<int> a) {
	n = a.size();
	vector<vector<int>> p(n + 1), pn(n + 1);
	for (int i = n - 1; ~i; --i) {
		if (a[i] > 0) {
			p[a[i]].push_back(i);
		}
		else {
			pn[-a[i]].push_back(i);
		}
	}
	fen.resize(n + 1);
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		if (a[i] < 0 && pn[-a[i]].back() == i) {
			int newi = i - query(i), newp = p[-a[i]].back() - query(p[-a[i]].back());
			ans += abs(newi - newp) - (newi < newp);
			update(i + 1, -1);
			update(p[-a[i]].back(), 1);
			p[-a[i]].pop_back();
			pn[-a[i]].pop_back();
		}
		else if (a[i] > 0 && p[a[i]].back() == i) {
			int newi = i - query(i), newp = pn[a[i]].back() - query(pn[a[i]].back());
			ans += abs(newp - newi) - (newp < newi);
			if (i) {
				update(i - 1, -1);
			}
			update(pn[a[i]].back(), 1);
			pn[a[i]].pop_back();
			p[a[i]].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