Submission #909397

#	Time	Username	Problem	Language	Result	Execution time	Memory
909397		Gray	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	384 ms	150060 KiB

shoes

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
const ll INF = 2e18;
const ll MOD = 1e9+7;
using namespace std;

struct Fenwick{
	vector<ll> t;
	ll n;
	Fenwick(ll sz){
		n = sz;
		t.resize(n+1, 0);
	}
	void update(ll i, ll ch){
		for (; i<=n; i+=(-i&i)) t[i]+=ch;
	}
	ll get(ll i){
		ll sum = 0;
		for (; i; i-=(-i&i)) sum+=t[i];
		return sum;
	}
};

long long count_swaps(vector<int> S){
	ll n = S.size()/2;
	Fenwick tr(2*n+1);
	for (ll i=0; i<2*n; i++){
		tr.update(i+1, 1);
	}
	unordered_map<ll, queue<ll>> pt;
	vector<ll> elp(2*n, -1);
	for (ll i=0; i<2*n; i++){
		if (pt[-S[i]].empty()) {
			pt[S[i]].push(i);
		}else{
			ll front = pt[-S[i]].front();
			pt[-S[i]].pop();
			elp[front]=i;
		}
	}
	ll ans = 0;
	for (ll i=0; i<2*n; i++){
		if (elp[i]==-1) continue;
		ll dif = tr.get(elp[i]+1)-tr.get(i+1)-1;
		if (S[i]>0){
			dif++;
		}
		ans+=dif;
		tr.update(elp[i]+1, -1);
		tr.update(i+1, -1);
	}
	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