Submission #143715

#	Time	Username	Problem	Language	Result	Execution time	Memory
143715		joseacaz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	650 ms	148444 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 100005;

int N;
vi BIT ( 2 * MAXN );
map<int, deque<int>> pos;

ll qry ( int x )
{
	x = N - x;
	ll res = 0;
	for ( ; x; x -= (x & -x) )
		res += BIT[x];
	return res;
}

void upd ( int x )
{
	x = N - x;
	for ( ; x < N; x += (x & -x) )
		BIT[x]++;
}

ll count_swaps ( vi s )
{
	N = s.size();
	vi nxt ( N, 0 ), vis ( N, 0 );
	ll ans = 0;
	for ( int i = 0; i < N; i++ )
	{
		if ( pos[-s[i]].empty() )
			pos[s[i]].push_back ( i + 1 );
		else
			nxt[pos[-s[i]].front() - 1] = i, pos[-s[i]].pop_front();
	}
	
	for ( int i = 0; i < N; i++ )
	{
		if ( vis[i] )
			continue;
		
		ans += (nxt[i] + qry(nxt[i])) - (i + qry(i)) - 1;
		upd ( nxt[i] );
		vis[nxt[i]] = 1;
		if ( s[i] > 0 )
			ans++;
	}
	
	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