Submission #363520

#	Time	Username	Problem	Language	Result	Execution time	Memory
363520		pavement	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	80 ms	17248 KiB

shoes

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

typedef long long ll;

vector<int> occ[200005];
int a[200005];
ll ft[200005];

inline int ls(int x) { return x & -x; }

ll qry(int p) {
	ll r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

void upd(int p) {
	for (; p <= 200000; p += ls(p)) ft[p]++;
}

ll count_swaps(vector<int> s) {
	vector<int> sz;
	int cnt = 0, n = s.size() / 2;
	for (int i : s) {
		occ[i + n].push_back(cnt++);
		if (i < 0) {
			sz.push_back(i);
			sz.push_back(-i);
		}
	}
	for (int i = 0; i <= 2 * n; i++) reverse(occ[i].begin(), occ[i].end());
	cnt = 0;
	for (int i : sz) {
		a[cnt++] = occ[i + n].back();
		occ[i + n].pop_back();
	}
	ll ans = 0;
	for (int i = 2 * n - 1; i >= 0; i--) {
		ans += qry(a[i] + 1);
		upd(a[i] + 1);
	}
	return ans;
}

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