Submission #580430

#	Time	Username	Problem	Language	Result	Execution time	Memory
580430		Sharky	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	309 ms	38424 KiB

shoes

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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

#ifndef EVAL
#include "grader.cpp"
#endif

const ll maxn = 200005;
vector<ll> fen(maxn, 0);
map<int, vector<int> > mp;

void upd (int id, ll val) {
	while (id <= maxn) {
		fen[id] += val;
		id += id & -id;
	}
}

ll pref (int id) {
	ll sum = 0;
	while (id > 0) {
		sum += fen[id];
		id -= id & -id;
	}
	return sum;
}

ll count_swaps(std::vector<int> trash) {
	int n = (int) trash.size();
	vector<int> s = {0}, pos(n+1, 0);
	vector<pair<int, int> > vec;
	for (int x : trash) s.push_back(x);
	for (int i = 1; i <= n; i++) mp[s[i]].push_back(i);
	ll ans = 0;
	for (int i = -n; i <= -1; i++) {
		for (int j = 0; j < sz(mp[i]); j++) {
			vec.push_back({mp[i][j], mp[-i][j]});
			if (vec.back().first > vec.back().second) swap(vec.back().first, vec.back().second), ans++;
		}
	}
	sort(all(vec));
	vector<int> v = {0};
	for (auto& [F, S] : vec) v.pb(F), v.pb(S);
	for (int i = 1; i <= n; i++) pos[v[i]] = i;
	for (int i = 1; i <= n; i++) {
		upd(pos[i], 1);
		ans = (ans - pref(pos[i]) + i); 
	}
	return ans;
}

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