Submission #914344

#	Time	Username	Problem	Language	Result	Execution time	Memory
914344		agusss	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	219 ms	37236 KiB

shoes

#include "vector"
#include "stdio.h"
#include "iostream"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
// using namespace __gnu_pbds;

typedef
__gnu_pbds::tree<
  int,
  __gnu_pbds::null_type,
  less<int>,
  __gnu_pbds::rb_tree_tag,
  __gnu_pbds::tree_order_statistics_node_update>
ordered_set;

struct Type { int v; };

struct SegmentTree {

  struct NodeType { int l, r, sum; };

  NodeType merge_nodes(NodeType a, NodeType b) {
    return { a.l, b.r, a.sum + b.sum };
  };

  NodeType set_leaf(int i, Type a) {
    return { i, i, a.v };
  }

  vector<NodeType> tree;

  vector<Type> *array;

  int left(int index) { return (index << 1) + 1; }

  int right(int index) { return (index << 1) + 2; }

  int mid(int l, int r) { return (l + r) >> 1; }

  bool on_left(NodeType a, int i) { return i <= mid(a.l, a.r); }

  void _build(int index, int l, int r) {
    if (l == r) {
      tree[index] = set_leaf(l, (*array)[l]); 
    } else {
      _build(left(index), l, mid(l, r));
      _build(right(index), mid(l, r) + 1, r);
      tree[index] = merge_nodes(tree[left(index)], tree[right(index)]);
    }
  }

  void build(vector<Type> &A) {
    array = &A;
    tree.resize((*array).size() * 4);
    _build(0, 0, (*array).size() - 1);
  }

  int u_i;

  Type u_v;

  void _update(int index) {
    if (tree[index].l == tree[index].r) {
      tree[index] = set_leaf(u_i, u_v);
      (*array)[u_i] = u_v;
    } else {
      if (on_left(tree[index], u_i)) {
        _update(left(index));
      } else {
        _update(right(index));
      }
      tree[index] = merge_nodes(tree[left(index)], tree[right(index)]);
    }
  }

  void update(int i, Type v) {
    u_i = i;
    u_v = v;
    _update(0);
  }

  int q_l;
  
  int q_r;
  
  NodeType _query(int index) {
    if (q_l <= tree[index].l and tree[index].r <= q_r) {
      return tree[index];
    }
    if (on_left(tree[index], q_r)) {
      return _query(left(index));
    }
    if (!on_left(tree[index], q_l)) {
      return _query(right(index));
    }
    return merge_nodes(_query(left(index)), _query(right(index))); 
  }

  NodeType query(int l, int r) {
    q_l = l;
    q_r = r;
    return _query(0);
  }
};

long long count_swaps(std::vector<int> s) {
  int n = s.size();
  long long cnt = 0;
  vector<Type> array(n);
  ordered_set os[n + 1];
  for (int i = 0; i < n; i++) {
    array[i] = { 1 };
    // cout << i << " = " << array[i].v << "\n";
    os[s[i] + (n >> 1)].insert(i);
  }
  SegmentTree ST;
  ST.build(array);
  // cout << "size:" << s.size() << "\n";
  for (int i = 0; i < (int)s.size(); i++) {
    if (array[i].v == 0) {
      continue;
    }
    // cout << "to pair" << i << "\n";
    int pair_index = -s[i] + (n >> 1);
    int j = os[pair_index].order_of_key(i + 1);
    // cout << "to pair " << i << "=> " << j << "\n";
    if (j < (int)os[pair_index].size()) {
      // cout << i << ": " << s[i] << " , "<< j << ": " << s[j] << "\n";
      auto it_j = os[pair_index].find_by_order(j);
      os[pair_index].erase(it_j);
      int j = *it_j;
      auto [ _, __, sum ] = ST.query(i, j);
      // cout << j << " sum = " << sum << "\n";
      ST.update(j, { 0 });
      long long distance = sum - (s[i] < 0 ? 2 : 1);
      cnt += distance;
    }
  }
	return cnt;
}

int mani() {

  vector<Type> B;

  int n;
  if (scanf("%d\n", &n));
  vector<int> A(n << 1);
  for (int i = 0; i < n << 1; i++) {
    if (scanf("%d", &A[i]));
  }
  // SegmentTree ST;
  // ST.build(B);
  // ST.print(10);
  printf("%lld\n", count_swaps(A));

  return 0;
}

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