Submission #891580

#	Time	Username	Problem	Language	Result	Execution time	Memory
891580		Arp	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	600 KiB

shoes

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 count_swaps(vector<int> arr){
  int n = arr.size();
  map<int,int> mp;
  vector<int> bit(n + 1);
  i64 ans = 0;
  for(int i = 0;i<n;i++){
    int e = arr[i];
    int ind;
    if(mp.find(-e) == mp.end()){
      ind = i + 1;
      mp[e] = ind;
    }else{
      ind = mp[-e];
      mp.erase(e); mp.erase(-e);
      ans += i; // implementation skills
      for(int j = ind;j > 0;j -= (j & -j)){
        ans -= bit[j];
      } 
      if(e < 0) ans ++;
    }
    // adding twice if found both the pair
    for(;ind <= n;ind += (ind & -ind)){
      bit[ind] ++;
    }
  }
  return ans;
}

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