Submission #304658

#	Time	Username	Problem	Language	Result	Execution time	Memory
304658		Temmie	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	384 KiB

shoes

#include <bits/stdc++.h>

typedef long long ll;

struct Seg {
	
	int size;
	std::vector <ll> v, w;
	
	Seg(int s) : size(s) {
		while (size < s) size <<= 1;
		v.resize(size * 2, 0);
		w.resize(size * 2, 0);
	}
	
	void add(int ind, ll val, int now, int l, int r) {
		if (r - l - 1) {
			v[now] += val;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) add(ind, val, now * 2 + 1, l, mid);
		else add(ind, val, now * 2 + 2, mid, r);
		v[now] = v[now * 2 + 1] + v[now * 2 + 2];
	}
	
	void add(int ind, ll val) {
		add(ind, val, 0, 0, size);
	}
	
	ll get(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r >= tl) return 0;
		if (l >= tl && r <= tr) return v[now];
		int mid = (l + r) >> 1;
		return get(tl, tr, now * 2 + 1, l, mid) + get(tl, tr, now * 2 + 2, mid, r);
	}
	
	ll get(int l, int r) {
		return get(l, r, 0, 0, size);
	}
	
};

ll count_swaps(std::vector <int> s) {
	int n = s.size();
	Seg seg(n);
	std::vector <std::vector <int>> ne(n + 1), po(n + 1);
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] < 0) ne[-s[i]].push_back(i);
		else po[s[i]].push_back(i);
	}
	ll r = 0;
	std::vector <bool> use(n, false);
	for (int i = 0; i < n; i++) {
		if (use[i]) continue;
		int targ;
		if (s[i] < 0) targ = po[-s[i]].back();
		else targ = ne[s[i]].back();
		r += ll(targ) + seg.get(0, targ) - ll(i) - seg.get(0, i) - ll(s[i] < 0);
		seg.add(0, 1);
		if (targ + 1 < n) seg.add(targ + 1, -1);
		use[i] = use[targ] = true;
		po[abs(s[i])].pop_back();
		ne[abs(s[i])].pop_back();
	}
	return r;
}

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