Submission #910210

#	Time	Username	Problem	Language	Result	Execution time	Memory
910210		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	368 ms	35020 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

template <class T1, // answer value stored on nodes
          class T2, // lazy update value stored on nodes
          T1 merge(T1, T1),
          void pushUpd(T2 & /*padre*/, T2 & /*hijo*/, int, int, int,
                       int), // push update value from a node to another.
                             // parent -> child
          void applyUpd(T2 &, T1 &, int,
                        int) // apply the update value of a node to its answer
                             // value. upd -> ans
          >
struct SegmentTreeLazy {
  vector<T1> ST;
  vector<T2> lazy;
  vector<bool> upd;
  int n;
  void build(int i, int l, int r, vector<T1> &values) {
    if (l == r) {
      ST[i] = values[l];
      return;
    }
    build(i << 1, l, (l + r) >> 1, values);
    build(i << 1 | 1, (l + r) / 2 + 1, r, values);
    ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
  }
  SegmentTreeLazy(vector<T1> &values) {
    n = values.size();
    ST.resize(n << 2 | 3);
    lazy.resize(n << 2 | 3);
    upd.resize(n << 2 | 3, false);
    build(1, 0, n - 1, values);
  }
  void push(int i, int l, int r) {
    if (upd[i]) {
      applyUpd(lazy[i], ST[i], l, r);
      if (l != r) {
        pushUpd(lazy[i], lazy[i << 1], l, r, l, (l + r) / 2);
        pushUpd(lazy[i], lazy[i << 1 | 1], l, r, (l + r) / 2 + 1, r);
        upd[i << 1] = 1;
        upd[i << 1 | 1] = 1;
      }
      upd[i] = false;
      lazy[i] = T2();
    }
  }
  void update(int i, int l, int r, int a, int b, T2 &u) {
    if (l >= a and r <= b) {
      pushUpd(u, lazy[i], a, b, l, r);
      upd[i] = true;
    }
    push(i, l, r);
    if (l > b or r < a)
      return;
    if (l >= a and r <= b)
      return;
    update(i << 1, l, (l + r) >> 1, a, b, u);
    update(i << 1 | 1, (l + r) / 2 + 1, r, a, b, u);
    ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
  }
  void update(int a, int b, T2 u) {
    if (a > b) {
      update(0, b, u);
      update(a, n - 1, u);
      return;
    }
    update(1, 0, n - 1, a, b, u);
  }
  T1 query(int i, int l, int r, int a, int b) {
    push(i, l, r);
    if (a <= l and r <= b)
      return ST[i];
    int mid = (l + r) >> 1;
    if (mid < a)
      return query(i << 1 | 1, mid + 1, r, a, b);
    if (mid >= b)
      return query(i << 1, l, mid, a, b);
    return merge(query(i << 1, l, mid, a, b),
                 query(i << 1 | 1, mid + 1, r, a, b));
  }
  T1 query(int a, int b) {
    if (a > b) {
      return merge(query(a, n - 1), query(0, b));
    }
    return query(1, 0, n - 1, a, b);
  }
  void get_leaves(int i, int l, int r, vector<T1> &res) {
    push(i, l, r);
    if (l == r) {
      res[l] = ST[i];
      return;
    }
    get_leaves(i << 1, l, (l + r) / 2, res);
    get_leaves(i << 1 | 1, (l + r) / 2 + 1, r, res);
  }
  void get_leaves(vector<T1> &res) {
    res.resize(n);
    get_leaves(1, 0, n - 1, res);
  }
};

void pushUpd(int &u1, int &u2, int l1, int r1, int l2, int r2) { u2 += u1; }

void applyUpd(int &u, int &v, int l, int r) { v += u; }

int merge(int a, int b) { return 0; }

ll count_swaps(vector<int> shoes) {
  ll swaps = 0;

  int n = shoes.size();

  vector<int> substract(n);
  SegmentTreeLazy<int, int, merge, pushUpd, applyUpd> STL(substract);

  map<int, set<int>> indexes;

  // [isFirstNegative, [i, j]]
  vector<pii> pairs;

  for (int i = 0; i < n; i++) {
    int shoe = shoes[i];

    if (indexes[-shoe].empty()) {
      indexes[shoe].insert(i);
      continue;
    }

    int index = *(indexes[-shoe].begin());
    indexes[-shoe].erase(index);

    pairs.emplace_back(index, i);
  }

  sort(pairs.begin(), pairs.end());

  for (auto &[left, right] : pairs) {
    int normalizedLeft = left + STL.query(left, left);
    int normalizedRight = right + STL.query(right, right);
    bool isFirstNegative = shoes[left] < 0;

    swaps += normalizedRight - normalizedLeft - isFirstNegative;

    STL.update(left, right, 1);
  }

  return swaps;
}

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