Submission #1049433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049433		Halit	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	242 ms	31572 KiB

shoes

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

struct SegmentTree {
  int N;
  std::vector<int> tree;
  std::vector<int> lazy;
  SegmentTree(int n) {
    N = n;
    tree.resize(4*N);
    lazy.resize(4*N);
  }
  void push(int node, int left, int right) {
    tree[node] += lazy[node] * (right - left + 1);
    if (left != right) {
      lazy[node*2] += lazy[node];
      lazy[node*2+1] += lazy[node];
    }
    lazy[node] = 0;
  }
  int get(int node, int left, int right, int idx) {
    push(node, left, right);
    if (left > idx || right < idx) {
      return 0;
    }
    if (left == idx && right == idx) {
      return tree[node];
    }
    return get(node*2, left, (left+right)/2, idx) + get(node*2+1, (left+right)/2+1, right, idx);
  }
  void add(int node, int left, int right, int tl, int tr) {
    push(node, left, right);
    if (left > tr || right < tl) {
      return;
    }
    if (left >= tl && right <= tr) {
      lazy[node] += 1;
      push(node, left, right);
      return;
    }
    add(node*2, left, (left+right)/2, tl, tr);
    add(node*2+1, (left+right)/2+1, right, tl, tr);
    tree[node] = tree[node*2] + tree[node*2+1];
  }
};

long long count_swaps(std::vector<int> s) {
	int n = s.size();
  std::map<int, std::vector<int>> idx;
  for (int i = n-1;i >= 0; --i) {
    idx[s[i]].push_back(i);
  }
  int64_t ans = 0;
  SegmentTree st(n);
  std::vector<bool> vis(n);
  for (int i = 0;i < n; ++i) {
    if (!vis[i]) {
      int next = idx[-s[i]].back();
      ans += next - i + st.get(1, 0, n-1, next) - st.get(1, 0, n-1, i) - (s[i] <= 0);
      st.add(1, 0, n-1, i, next);
      vis[next] = true;
      idx[s[i]].pop_back();
      idx[-s[i]].pop_back();
    }
  }
  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