Submission #200921

#	Time	Username	Problem	Language	Result	Execution time	Memory
200921		Lawliet	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	48 ms	5236 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];
};

vector< int > L;
vector< int > R;

bool marc[MAXN];

FenwickTree BIT;

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

	for(int i = 1 ; i <= n ; i++)
	{
		if( s[i - 1] < 0 ) L.push_back( i );
		else R.push_back( i );
	}

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

	lli ans = 0;
	int last = 0;

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

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

		marc[ R[last] ] = true;

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

	return ans;
}

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