Submission #1169289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169289		catch_me_if_you_can	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	65 ms	22852 KiB

shoes

#include<bits/stdc++.h>
#define int long long
#include "shoes.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

struct fenwick
{
	vector<int> val;
	int N;
	void init(int n)
	{
		N = n+5;
		val.assign(N, 0);
		return;
	}
	int sum(int x)
	{
		int ret = 0;
		for(int t = x; t; t-=(t&-t))
			ret+=val[t];
		return ret;
	}
	void upd(int x)
	{
		for(int t = x; t < N; t+=(t&-t))
			val[t]++;
		return;
	}
};

int count_swaps(vector<signed> s)
{
	int n = (s.size())/2;
	set<int> p[2*n+1];
	for(int i = 0; i < 2*n; i++)
		p[s[i]+n].insert(i);
	vector<in> pr;
	int ans = 0;
	for(int i = 0; i < 2*n; i++)
	{
		if(p[s[i]+n].find(i) == p[s[i]+n].end())
			continue;//already paired.
		if(s[i] > 0)
			ans++;
		auto fn = p[-s[i]+n].lower_bound(i);
		pr.pb({i, *fn});
		p[s[i]+n].erase(i);
		p[-s[i]+n].erase(fn);
	}
	sort(pr.begin(), pr.end());
	fenwick fen; fen.init(2*n);
	for(auto [l, r]: pr)
	{
		ans+=(r-l-1); ans-=(fen.sum(r+1)-fen.sum(l));
		fen.upd(r+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