Submission #978018

#	Time	Username	Problem	Language	Result	Execution time	Memory
978018		kilkuwu	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	443 ms	36268 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>

struct SegmentTree {
  int n;
  std::vector<int> t;

  SegmentTree(int _n) : n(_n), t(2 * n) {}

  void update(int l, int r, int v) {
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) t[l] += v, l++;
      if (r & 1) --r, t[r] += v;
    }
  }

  int query(int p) {
    int ans = 0;
    for (p += n; p > 0; p >>= 1) {
      ans += t[p];
    }
    return ans;
  }
};

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

  int n = (int) s.size() / 2;
  SegmentTree tree(2 * n);

  for (int i = 0; i < 2 * n; i++) {
    tree.update(i, i + 1, i);
  }

  std::map<int, std::vector<int>> mp;

  std::set<std::pair<int, int>> st;
  for (int i = 2 * n; i >= 0; i--) {
    mp[s[i]].push_back(i);
    st.insert({i, s[i]});
  }

  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int f = 2 * i; 
    int v = st.begin()->second;

    auto pos = mp[-v].back();
    mp[-v].pop_back();
    mp[v].pop_back();

    int real_pos = tree.query(pos);
    ans += real_pos - (f + (v < 0));
    tree.update(0, pos, 1);
    st.erase(st.begin());
    st.erase({pos, s[pos]});
  }

  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