Submission #1237111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237111		MuhammadSaram	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	224 ms	272436 KiB

shoes

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

using namespace std;

const int M = 2e5 + 1;

int fen[M];

void modify(int p,int x)
{
	while (p<M)
		fen[p]+=x,p+=p&-p;
}

int get(int p)
{
	int ans=0;
	while (p)
		ans+=fen[p], p^=p&-p;
	return ans;
}

long long count_swaps(vector<int> a)
{
	int n=a.size();
	queue<int> ind[n+1][2];
	for (int i=0;i<n;i++)
		modify(i+1,1);
	long long ans=0;
	for (int i=0;i<n;i++)
	{
		int x=abs(a[i]);
		ind[x][a[i]>0].push(i);
		if (min(ind[x][0].size(),ind[x][1].size())==1)
		{
			ans+=get(ind[x][0].front()), modify(ind[x][0].front()+1,-1);
			ans+=get(ind[x][1].front()), modify(ind[x][1].front()+1,-1);
			ind[x][0].pop(), ind[x][1].pop();
		}
	}
	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