Submission #891586

#	Time	Username	Problem	Language	Result	Execution time	Memory
891586		Arp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	394 ms	148048 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,queue<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[-e].empty()){
      ind = i + 1;
      mp[e].push(ind);
    }else{
      ind = mp[-e].front();
      mp[-e].pop();
      ans += i; 
      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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15