Submission #796627

#	Time	Username	Problem	Language	Result	Execution time	Memory
796627		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	256 ms	26776 KiB

shoes

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

#define ll long long
#define vi vector<int>

vector<ll> tr;
void init(int n){
  tr.assign(n,1);
  for(int i=0;i<n;i++){
    int j=i|(i+1);
    if(j<n) tr[j]+=tr[i];
  }
}
void upd(int i){
  for(;i<(int)tr.size();i|=i+1) tr[i]--;
}
ll get(int i){
  ll res=0;
  for(;i>=0;i=(i&(i+1))-1) res+=tr[i];
  return res;
}
ll get(int i, int j){
  return get(j-1)-get(i);
}

long long count_swaps(vi s) {
	int n=s.size();

	map<int,priority_queue<int,vi,greater<int>>> ma;
	for(int i=0;i<n;i++) ma[s[i]].push(i);

	init(n);
	
	ll res=0;
	bool taken[n]={};
	for(int i=0;i<n;i++){
	  if(taken[i]) continue;

	  int j=ma[-s[i]].top();
	  ma[-s[i]].pop();
	  ma[s[i]].pop();
	  
	  res+=get(i,j)+(s[i]>0);
	  upd(j);

	  taken[i]=taken[j]=true;
	}
	
	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