Submission #287209

#	Time	Username	Problem	Language	Result	Execution time	Memory
287209		Haunted_Cpp	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	117 ms	33688 KiB

shoes

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

using namespace std;

const int MAX_N = 5e5 + 5;

vector<vector<int>> L(MAX_N), R(MAX_N);
bitset<MAX_N> solved;

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

long long count_swaps(vector<int> s) {
  const int n = s.size();
  for (int i = 0; i < n; i++) {
    const int cur = abs(s[i]);
    if (s[i] < 0) {
      L[cur].emplace_back(i);
    } else {
      R[cur].emplace_back(i);
    }
  }
  for (int i = 0; i < MAX_N; i++) {
    reverse(L[i].begin(), L[i].end());
    reverse(R[i].begin(), R[i].end());
  }
  FenwickTree fen(n);
  auto get_idx = [&](int idx) {
    return idx + fen.query(idx);
  };
  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (solved[i]) continue;
    const int cur = abs(s[i]);
    int lo = i;
    int hi;
    if (s[i] > 0) {
      R[cur].pop_back();
      hi = L[cur].back();
      L[cur].pop_back();
    } else {
      L[cur].pop_back();
      hi = R[cur].back();
      R[cur].pop_back();
    }
    solved[lo] = solved[hi] = 1;
    res += (s[i] > 0) + get_idx(hi) - get_idx(lo) - 1;
    fen.range_update(lo, hi, + 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