Submission #724243

#	Time	Username	Problem	Language	Result	Execution time	Memory
724243		badont	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	75 ms	17176 KiB

shoes

#include "shoes.h"
#include <cmath>
#include <cstdlib> 
#include <cassert>

using ll = long long;
using namespace std;

template<typename T>
struct fen {
	vector<T> tr;
	ll mxn;

	fen(ll sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(ll g, T k) {
    g++;
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(ll g) {
    g++;
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(ll l, ll r) { if (l > r) return 0; return ge(r) - ge(l - 1); }
};

long long count_swaps(std::vector<int> s) {
	ll n = (ll)s.size();
	n /= 2;
	vector<vector<ll>> pos(n, vector<ll>()), neg(n, vector<ll>());	

	for (int i = 0; i < 2 * n; i++) {
		ll x = abs(s[i]);
		if (s[i] < 0) {
			neg[x - 1].push_back(i);
		} else {
			pos[x - 1].push_back(i);
		}
	}

	ll op_1 = 0, op_2 = 0;
	vector<ll> match(2 * n);
	for (int i = 0; i < n; i++) {
		assert(neg[i].size() == pos[i].size());
		for (int j = 0; j < (int)neg[i].size(); j++) {
			ll x = neg[i][j], y = pos[i][j];
      match[x] = y;
      match[y] = x;
			if (x > y) op_2++;
		}
	}

  fen<ll> tree(2 * n);
  for (int i = 0; i < 2 * n; i++)
    tree.upd(i, 1);

  for (int i = 0; i < 2 * n; i++) if (match[i] > i) {
    op_1 += tree.rng(i + 1, match[i]) - 1;
    tree.upd(match[i], -1);
  }
 
   return op_1 + op_2;

}

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