제출 #786322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786322		12345678	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	232 ms	274380 KiB

shoes

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

using namespace std;

const int nx=2e5+5;

int n;
long long ans;
queue<int> q[2][nx];
bool used[nx];

struct fenwick
{
	int d[nx];
	void add(int idx, int vl)
	{
		while (idx<nx) d[idx]+=vl, idx+=(idx&-idx); 
	}
	int find(int idx)
	{
		int tmp=0;
		while (idx>0) tmp+=d[idx], idx-=(idx&-idx);
		return tmp;
	}
} f;

long long count_swaps(std::vector<int> s) {
	int n=s.size();
	for (int i=1; i<=n; i++)
	{
		if (s[i-1]<0) q[0][-s[i-1]].push(i);
		else q[1][s[i-1]].push(i);
	}
	for (int i=1; i<=n; i++) f.add(i, 1);
	for (int i=1; i<=n; i++)
	{
		if (used[i]) continue;
		int sz=s[i-1];
		if (sz<0)
		{
			q[0][-sz].pop();
			int p=q[1][-sz].front(), cl=f.find(i), pl=f.find(p);
			q[1][-sz].pop();
			used[p]=1;
			ans+=(pl-cl-1);
			f.add(i, 1); f.add(p+1, -1);
		}
		else
		{
			q[1][sz].pop();
			int p=q[0][sz].front(), cl=f.find(i), pl=f.find(p);
			q[0][sz].pop();
			used[p]=1;
			ans+=(pl-cl);
			f.add(i, 1); f.add(p+1, -1);
		}
	}
	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