Submission #226150

#	Time	Username	Problem	Language	Result	Execution time	Memory
226150		Haunted_Cpp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	170 ms	21992 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

const int OFF = 1e5 + 5;
const int N = 2 * OFF;

bitset<N> is_used;
vector< set<int> > g (N);

template<typename T>
struct FenwickTree {
  vector<T> bit;
  const int N;
  FenwickTree (int n) : N (n + 5) {
    bit.clear();
    bit.resize(N);
  }
  void update (int idx, T delta) {
    for (; idx < N; idx += idx & (- idx)) {
      bit[idx] += delta;
    }
  }
  void range_update (int lo, int hi, T delta) {
    update (lo, + delta);
    update (hi + 1, - delta);
  }
  T query (int idx) {
    T res {};
    for (; idx > 0; idx -= idx & (- idx)) {
      res += bit[idx];
    }
    return res;
  }
};

long long count_swaps(vector<int> s) {
  long long res = 0;
  const int n = (int) s.size();
  FenwickTree<int> fen (N);
  s.insert (s.begin(), 0);
  is_used.reset();
  for (int i = 1; i <= n; i++) {
    g[s[i] + OFF].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    if (is_used.test(i)) continue;
    int delta = s[i] * -1;
    int cur = i;
    int nxt = *g[delta + OFF].begin(); 
    is_used.set(cur);
    is_used.set(nxt);
    int p1 = cur + fen.query (cur);
    int p2 = nxt + fen.query (nxt);
    res += p2 - p1 - (s[i] < 0);
    g[s[i] + OFF].erase(i);
    g[delta + OFF].erase(nxt);
    fen.range_update (cur + 1, nxt - 1, + 1); 
  }
	return res;
}

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