Submission #298621

#	Time	Username	Problem	Language	Result	Execution time	Memory
298621		kevlee	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	117 ms	15864 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[200005], negpointer[100005], pospointer[100005];
vi neg[100005], pos[100005];
bool used[200005];
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) {
      pos[a[i-1]].pb(i);
    } else {
      neg[-a[i-1]].pb(i);
    }
  }
  ll ans = 0;
  FOR(i, 1, n) {
    if (used[i]) continue;
    if (a[i-1] < 0) {
      update(i, -1);
      ans += query(pos[-a[i-1]][pospointer[-a[i-1]]] - 1);
      update(pos[-a[i-1]][pospointer[-a[i-1]]], -1);
      used[pos[-a[i-1]][pospointer[-a[i-1]]]] = true;
      pospointer[-a[i-1]]++;
      negpointer[-a[i-1]]++;
    } else {
      update(i, -1);
      //cout << neg[a[i-1]][negpointer[a[i-1]]] << endl;
      ans += query(neg[a[i-1]][negpointer[a[i-1]]] - 1) + 1;
      update(neg[a[i-1]][negpointer[a[i-1]]], -1);
      used[neg[a[i-1]][negpointer[a[i-1]]]] = true;
      pospointer[a[i-1]]++;
      negpointer[a[i-1]]++;
    }
    //cout << i << ' ' << ans << endl;
  }
  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