Submission #304712

#	Time	Username	Problem	Language	Result	Execution time	Memory
304712		Temmie	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	177 ms	23104 KiB

shoes

#include <bits/stdc++.h>

typedef long long ll;

struct Seg {
	
	int size;
	std::vector <ll> v;
	
	Seg(int s) : size(1) {
		while (size < s) size <<= 1;
		v.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[abs(s[i])].push_back(i);
		else po[abs(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 = s[i] < 0 ? po[abs(s[i])].back() : ne[abs(s[i])].back();
		po[abs(s[i])].pop_back(); ne[abs(s[i])].pop_back(); use[targ] = true;
		r += ll(targ - i - 1) + seg.get(i, targ + 1) + ll(s[targ] < 0);
		seg.add(targ, -1);
	}
	return r;
}

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