Submission #378485

#	Time	Username	Problem	Language	Result	Execution time	Memory
378485		autumn_eel	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	700 ms	41836 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;

struct BIT{
	vector<int>bit;
	BIT(int n){
		bit=vector<int>(n+10);
	}
	void add(int k,int x){
		k++;
		while(k<(int)bit.size()){
			bit[k]+=x;
			k+=k&-k;
		}
	}
	int sum(int k){
		k++;
		int res=0;
		while(k){
			res+=bit[k];
			k-=k&-k;
		}
		return res;
	}
};

long long count_swaps(std::vector<int> s) {
	BIT bit(s.size());
	map<int,set<int>>mp;
	set<int>se;
	rep(i,s.size()){
		se.insert(i);
		mp[s[i]].insert(i);
		bit.add(i,1);
	}
	ll ans=0;
	while(!se.empty()){
		int x=*se.begin();se.erase(se.begin());
		mp[s[x]].erase(mp[s[x]].begin());
		int y=*mp[-s[x]].begin();mp[-s[x]].erase(mp[-s[x]].begin());
		se.erase(y);
		bit.add(x,-1);
		bit.add(y,-1);
		int cnt=bit.sum(y);
		if(s[x]>0)cnt++;
		ans+=cnt;
	}
	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