Submission #764582

#	Time	Username	Problem	Language	Result	Execution time	Memory
764582		zsombor	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	70 ms	72436 KiB

shoes

#include <iostream>
#include <vector>
#include <queue>
#include "shoes.h"
using namespace std;

int n, a, b;
long long ans = 0;
vector <queue <int>> v(1e5 + 1);
vector <int> p(2e5, -1);
vector <int> fen(2e5, 0);

void update(int r) {
	for (int i = r; i >= 0; i = (i & (i + 1)) - 1) fen[i]++;
}

int query(int x) {
	int ret = 0;
	for (int i = x; i < 2 * n; i = (i | (i + 1))) ret += fen[i];
	return ret;
}

long long count_swaps(vector <int> S) {
	n = S.size() / 2;
	for (int i = 0; i < 2 * n; i++) {
		if (!v[abs(S[i])].size() || S[i] == S[v[abs(S[i])].front()]) {
			v[abs(S[i])].push(i);
			continue;
		}
		p[v[abs(S[i])].front()] = i;
		v[abs(S[i])].pop();
	}
	for (int i = 0; i < 2 * n; i++) {
		if (p[i] == -1) continue;
		a = i + query(i), b = p[i] + query(p[i]);
		ans += b - a - 1;
		if (S[i] > 0) ans++;
		update(p[i]);
	}
	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