Submission #226113

#	Time	Username	Problem	Language	Result	Execution time	Memory
226113		Haunted_Cpp	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	14 ms	11648 KiB

shoes

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

using namespace std;


const int OFF = 1e5 + 5;
const int N = 2 * OFF;

bitset<N> is_valid;
vector<int> g [N];

struct FenwickTree {
  vector<int> bit;
  const int N;
  FenwickTree (int n) : N (n + 5) {
    bit.clear (); bit.resize (N);
  }
  void update (int idx, int delta) {
    for (; idx < N; idx += idx & (- idx)) {
      bit[idx] += delta;
    }
  }
  void range_update (int lo, int hi, int delta) {
    update (lo, + delta);
    update (hi + 1, - delta);
  }
  int query (int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & (- idx)) {
      res += bit[idx];
    }
    return res;
  }
};

long long count_swaps(vector<int> s) {
  long long res = 0;
  const int n = (int) s.size();
  FenwickTree fen (N);
  s.insert (s.begin(), 0);
  for (int i = 1; i <= n; i++) {
    g[s[i] + OFF].emplace_back(i);
  }
  is_valid.set();
  for (int i = 1; i <= n; i++) {
    if (is_valid.test(i) == 0) continue;
    int delta = s[i] * -1;
    int cur = i;
    int nxt = *lower_bound (g[delta + OFF].begin(), g[delta + OFF].end(), i);
    is_valid[cur] = is_valid[nxt] = 0;
    assert (cur < nxt);
    int p1 = cur + fen.query (cur);
    int p2 = nxt + fen.query (nxt);
    assert (p1 < p2);  
    res += p2 - p1 - (delta > 0);
    fen.range_update (cur + 1, nxt - 1, + 1);      
  }
	return res;
}

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