Submission #230182

#	Time	Username	Problem	Language	Result	Execution time	Memory
230182		chubyxdxd	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	205 ms	31816 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll tree[200100];
ll tam;
void update(ll pos,ll val){
  while(pos<=tam){
    tree[pos]+=val;
    pos+=(pos&-pos);
  }
}
ll query(ll pos){
  ll curr=0;
  while(pos>0){
    curr+=tree[pos];
    pos-=(pos&-pos);
  }
  return curr;
}
unordered_map<ll,set<ll> > mp;
long long count_swaps(std::vector<int> s) {
  tam=s.size();
  bool vis[tam];
  memset(vis,false,sizeof vis);
  for(int i=0;i<tam;i++){
    mp[s[i]].insert(i);
  }
  set<ll>::iterator it,it1;
  ll ans=0;
  for(int i=0;i<tam-1;i++){
    if(vis[i])continue;
    vis[i]=true;
    mp[s[i]].erase(i);
    if(s[i]>0){
      it=mp[(s[i]*-1)].begin();
      mp[s[i]*-1].erase(it);
      ll aux=*it;
      ll curr=i+query(i+1ll);
      ll curr1=aux+query(aux+1ll);
      ll currans=curr1-curr;
      vis[aux]=true;
      update(i+1,1);
      update(aux+1,-1);
      ans+=currans;
    }
    else{
      it=mp[s[i]*-1].begin();
      mp[s[i]*-1].erase(it);
      ll aux=*it;
      ll curr=i+query(i+1ll);
      ll curr1=aux+query(aux+1ll);
      ll currans=curr1-(curr+1);
      ans+=currans;
      vis[aux]=true;
      //cout<<currans<<endl;
      if(currans!=0){
	update(i+2,1);
	update(aux+1,-1);
      }
    }
  }
  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