Submission #1088463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088463		LucasLe	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	52 ms	16580 KiB

shoes

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

using namespace std;
const int maxn = 1e6 + 5;

int n;
long long fen[maxn + 5];

void update(int v, int x) {
  for (; v <= 2 * n; v += v & (-v)) {
    fen[v] += x;
  }
}

long long get(int v) {
  long long ans = 0;
  for (; v; v -= v & (-v))
    ans += fen[v];
  return ans;
}

long long count_swaps(vector<int> s) {
  n = (int)s.size() / 2;
  vector<int> L[n + 1], R[n + 1];
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] < 0) L[-s[i]].push_back(i + 1);
    else R[s[i]].push_back(i + 1);
  }
  long long res = 0;
  vector<pair<int, int>> vec;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < (int)L[i].size(); ++j) {
      int p1 = L[i][j], p2 = R[i][j];
      if (p1 > p2) {
        res++;
        swap(p1, p2);
      }
      vec.push_back({p1, p2});
    }
  }
  sort(vec.begin(), vec.end());
  for (int i = 0; i < (int)vec.size(); ++i) {
    long long s1 = get(vec[i].first);
    long long s2 = get(vec[i].second);
    res += s2 - s1 + 2ll * (i - s2);
    update(vec[i].second, 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