제출 #1237102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237102		MuhammadSaram	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	21 ms	3776 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();
	vector<int> v[2];
	for (int i=0;i<n;i++)
		modify(i+1,1), v[a[i]>0].push_back(i);
	reverse(v[0].begin(), v[0].end());
	reverse(v[1].begin(), v[1].end());
	long long ans=0;
	for (int i=0;i<n;i++)
		ans+=get(v[i%2].back()),modify(v[i%2].back()+1,-1),v[i%2].pop_back();
	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