Submission #941421

#	Time	Username	Problem	Language	Result	Execution time	Memory
941421		Numberz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	132 ms	140296 KiB

shoes

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


const int Mx = 200005;
int arr[Mx];
int used[Mx];


//fenwick tree functions
void add(int index, int x) {
  index++;
  while (index < Mx) {
    arr[index] += x;
    index += index & -index;
  }
}

int get(int index) {
  index++;
  int r = 0;
  while (index > 0) {
    r += arr[index];
    index -= index & -index;
  }
  return r;
}


long long count_swaps(std::vector<int> s) {

  //build the trees
  int n = s.size() / 2;
  queue<int> right[n+1], left[n+1];
  for (int i = 0; i < n*2; i++) {
    if (s[i] > 0) right[s[i]].push(i+1);
    else left[-s[i]].push(i+1);
  }

  //same idea as before, go through, but with fenwick
  long long ans = 0;
  for (int i = 0; i < n*2; i++) {
    if (used[i+1]) continue;
    
    int x = right[abs(s[i])].front();
    int y = left[abs(s[i])].front();
    right[abs(s[i])].pop();
    left[abs(s[i])].pop();

    if (s[i] > 0) {
      ans += y - x - (get(y) - get(x));
      add(y, 1);
    } else {
      ans += x - y - (get(x) - get(y)) - 1;
      add(x, 1);
    }
    used[y] = 1;
    used[x] = 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