Submission #550282

#	Time	Username	Problem	Language	Result	Execution time	Memory
550282		pere_gil	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	171 ms	27816 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;

#define index int med=(s+e)/2,l=2*n+1,r=2*n+2
typedef long long ll;
const int tam=2e5+5;
unordered_map<int,priority_queue<int,vector<int>,greater<int>>> ma;
vector<int> tr(4*tam);

void init(int n, int s, int e){
	if(s==e){
		tr[n]=1;
		return;
	}
	index;
	init(l,s,med); init(r,med+1,e);
	tr[n]=tr[l]+tr[r];
}
void update(int n, int s, int e, int pos){
	if(s==e){
		tr[n]=0;
		return;
	}
	index;
	if(pos<=med) update(l,s,med,pos);
	else update(r,med+1,e,pos);
	tr[n]=tr[l]+tr[r];
}
int query(int n, int s, int e, int i, int j){
	if(i>j) return 0;
	if(i<=s && e<=j) return tr[n];
	index;
	if(j<=med) return query(l,s,med,i,j);
	if(i>med) return query(r,med+1,e,i,j);
	return query(l,s,med,i,j)+query(r,med+1,e,i,j);
}

long long count_swaps(std::vector<int> s) {
	int n=s.size();
	for(int i=0;i<n;i++) ma[s[i]].push(i);
	init(0,0,n-1);
	
	ll res=0;
	vector<bool> vis(n,false);
	for(int i=0;i<n;i++){
		if(vis[i]) continue;
		int j=ma[-s[i]].top();
		ma[-s[i]].pop();
		ma[s[i]].pop();
		vis[j]=true;
		res+=query(0,0,n-1,i+1,j-1)+(s[i]>0);
		update(0,0,n-1,j);
	}

	return res;
}

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