Submission #298611

#	Time	Username	Problem	Language	Result	Execution time	Memory
298611		kevlee	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	39 ms	9856 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define inf 1000000000
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int n, bit[100005], pointer[100005];
vi v[100005];
void update(int x, int upd) {
  for (int i = x; i <= n; i += (i & (-i))) {
    bit[i] += upd;
  }
}
int query(int x) {
  int ret = 0;
  for (int i = x; i > 0; i -= (i & (-i))) {
    ret += bit[i];
  }
  return ret;
}
long long count_swaps(vector<int> a) {
	n = a.size();
  FOR(i, 1, n) {
    update(i, 1);
    if (a[i-1] > 0) {
      v[a[i-1]].pb(i);
    }
  }
  ll ans = 0;
  FOR(i, 1, n) {
    if (a[i-1] < 0) {
      ans += query(i - 1);
      update(i, -1);
      ans += query(v[-a[i-1]][pointer[-a[i-1]]] - 1);
      update(v[-a[i-1]][pointer[-a[i-1]]], -1);
      pointer[-a[i-1]]++;
    }
  }
  return ans;
}

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