Submission #208336

#	Time	Username	Problem	Language	Result	Execution time	Memory
208336		alexxela12345	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	604 ms	54156 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> tree;

void add(int v, int l, int r, int ind) {
  if (ind < l || ind >= r) {
    return;
  }
  tree[v] += 1;
  if (l + 1 != r) {
    int m = l + (r - l) / 2;
    add(2 * v + 1, l, m, ind);
    add(2 * v + 2, m, r, ind);
  }
}

ll get(int v, int l, int r, int ql, int qr) {
  if (r <= ql || qr <= l) {
    return 0;
  }
  if (ql <= l && r <= qr) {
    return tree[v];
  }
  int m = l + (r - l) / 2;
  return get(2 * v + 1, l, m, ql, qr) + 
         get(2 * v + 2, m, r, ql, qr);
}

ll count_swaps(vector<int> a) {
  int n = a.size() / 2;
  ll ans = 0;
  map<int, vector<int>> last;
  vector<int> pr(2 * n, -1);
  for (int i = 2 * n - 1; i >= 0; i--) {
    last[a[i]].push_back(i);
  }
  for (int i = 0; i < 2 * n; i++) {
    if (pr[i] != -1)
      continue;
    pr[i] = last[-a[i]].back();;
    last[-a[i]].pop_back();
    last[a[i]].pop_back();
    ans += abs(pr[i] - i) - 1;
    if ((pr[i] > i) != (a[pr[i]] > a[i])) {
      ans++;
    }
    pr[pr[i]] = i;
  }
  vector<vector<int>> q;
  for (int i = 0; i < 2 * n; i++) {
    q.push_back({i});
    if (pr[i] > i) {
      // count pr[j] > pr[i] | j in [i, pr[i]]
      q.push_back({i, pr[i] + 1, -1});
      q.push_back({pr[i], pr[i] + 1, 1});
    }
  }
  tree.resize(8 * n);
  sort(q.begin(), q.end());
  for (auto &el : q) { 
    if (el.size() == 1) {
      add(0, 0, 2 * n, pr[el[0]]);
    } else {
      int x = get(0, 0, 2 * n, el[1], 2 * n);
      ans -= x * el[2];
    }
  }
  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