Submission #154317

#	Time	Username	Problem	Language	Result	Execution time	Memory
154317		arman_ferdous	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	44 ms	7272 KiB

shoes

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

using ll = long long;
const int N = 1e5+100;

int bit[N];
void upd(int pos, int x) {
	while(pos < N) bit[pos] += x, pos += pos&-pos;
}
ll pref(int pos, ll r = 0) {
	while(pos > 0) r += bit[pos], pos -= pos&-pos;
	return r;
}
ll get(int l, int r) {
	if(r < l) return 0;
	return pref(r) - pref(l - 1);
}

int idx[N], ryt[N];
long long count_swaps(vector<int> s) {
	int n = s.size();
	s.insert(s.begin(), 0);

	memset(idx, -1, sizeof idx);
	memset(ryt, -1, sizeof ryt);
	for(int i = n; i > 0; i--) {
		upd(i, +1);
		if(idx[abs(s[i])] != -1) {
			ryt[i] = idx[abs(s[i])];
			idx[abs(s[i])] = -1;
		} else idx[abs(s[i])] = i;
	}

	ll ret = 0;
	for(int i = 1; i <= n; i++) if(ryt[i] + 1) {
		ret += get(i + 1, ryt[i] - 1);
		ret += (s[ryt[i]] < 0);
		upd(ryt[i], -1);
	}
	return ret;
}

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