Submission #200923

#	Time	Username	Problem	Language	Result	Execution time	Memory
200923		Lawliet	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	120 ms	20216 KiB

shoes

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

using namespace std;
typedef long long int lli;

const int MAXN = 200010;

class FenwickTree
{
	public:

		void update(int i, int v)
		{
			for( ; i < MAXN ; i += i & -i )
				BIT[i] += v;
		}

		int query(int i)
		{
			int ans = 0;

			for( ; i > 0 ; i -= i & -i )
				ans += BIT[i];

			return ans;
		}

		int sum(int L, int R) { return query( R ) - query( L - 1 ); }

		FenwickTree() { memset( BIT , 0 , sizeof(BIT) ); }

	private:

		int BIT[MAXN];
};

int last[MAXN];

vector< int > L[MAXN];
vector< int > R[MAXN];

bool marc[MAXN];

FenwickTree BIT;

long long count_swaps(vector<int> s) 
{
	int n = s.size();

	for(int i = 1 ; i <= n ; i++)
	{
		int val = abs( s[i - 1] );

		if( s[i - 1] < 0 ) L[ val ].push_back( i );
		else R[ val ].push_back( i );
	}

	for(int i = 1 ; i <= n ; i++)
		BIT.update( i , 1 );

	lli ans = 0;

	for(int i = 1 ; i <= n ; i++)
	{
		if( marc[i] ) continue;

		int val = abs( s[i - 1] );

		if( s[i - 1] > 0 )
		{
			ans++;
			swap( L[val][ last[val] ] , R[val][ last[val] ] );
		}

		marc[ R[val][ last[val] ] ] = true;

		ans += BIT.sum( L[val][ last[val] ] + 1 , R[val][ last[val] ] ) - 1;
		BIT.update( R[val][ last[val] ] , -1 ); 
		
		last[val]++;
	}

	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