Submission #159125

#	Time	Username	Problem	Language	Result	Execution time	Memory
159125		kig9981	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	64 ms	9468 KiB

shoes

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

using namespace std;

vector<int> P[100001];
int tree[200001];

void update(int n, int v)
{
	for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}

int get_cnt(int n)
{
	int ret=0;
	for(++n;n;n-=n&-n) ret+=tree[n];
	return ret;
}

long long count_swaps(vector<int> S)
{
	int N=S.size();
	long long ret=0;
	for(int i=N-1;i>=0;i--) {
		if(S[i]>0) P[S[i]].push_back(i);
		update(i,1);
	}
	for(int i=0;i<N;i++) if(S[i]<0) {
		update(i,-1);
		ret+=get_cnt(i);
		update(P[-S[i]].back(),-1);
		ret+=get_cnt(P[-S[i]].back());
		P[-S[i]].pop_back();
	}
	return ret;
}

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