Submission #289867

#	Time	Username	Problem	Language	Result	Execution time	Memory
289867		Bill_00	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	328 ms	275832 KiB

shoes

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

using namespace std;
queue<int> l[200005], r[200005];
long long s[200005];
int a[200005];
int n;
long long tree[1000005];
void add(int i, int x)
{
	while(i <= 2 * n)
	{
		s[i] += x;
		i += (i & (-i));
	}
}
long long sum(int i)
{
	long long res = 0;
	while(i > 0)
	{
		res += s[i];
		i -= (i & (-i));
	}
	return res;
}
long long count_swaps(vector<int> b)
{
  	int i, j;
	n = b.size() / 2;
	for(i = 1; i <= 2 * n; i++) a[i] = b[i - 1];
	long long ans = 0;
	cin >> n;
	for(i = 1; i <= 2 * n; i++) 
	{
		cin >> a[i];
		if(a[i] > 0) r[a[i]].push(i);
		else l[-a[i]].push(i);
	}
	for(i = 1; i <= 2 * n; i++) add(i, 1);
	for(i = 1; i <= 2 * n; i++) if(sum(i) - sum(i - 1)){
		if(a[i] < 0)
		{
			
			int id;
			id = r[-a[i]].front();
			ans += sum(id) - sum(i) - 1;
			add(id, -1);
			l[-a[i]].pop();
			r[-a[i]].pop();
		}
		else {
			int id;
			id = l[a[i]].front();
			ans += sum(id) - sum(i);
			add(id, -1);
			l[a[i]].pop();
			r[a[i]].pop();
		}
	}
	return ans;
}
/*
6
-2 2 2 -2 -2 2
*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:30:11: warning: unused variable 'j' [-Wunused-variable]
   30 |    int i, j;
      |           ^

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