Submission #226110

#	Time	Username	Problem	Language	Result	Execution time	Memory
226110		Haunted_Cpp	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	16 ms	11904 KiB

shoes

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

using namespace std;

const int N = 2e5 + 5;
bitset<2 * N> is_valid;

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();
  const int OFF = N + 5;
  vector<int> g [N + 5000]; 
  for (int i = 0; i < n; i++) {
    g[s[i] + OFF].emplace_back(i);
  }
  FenwickTree fen (N + 5000); 
  for (int i = 0; i < n; i++) {
    if (is_valid[i] == true) continue; 
    int target = s[i] * -1;
    int primeiro = i + fen.query (i + 1);
    int p = *lower_bound(g[target + OFF].begin(), g[target + OFF].end(), i);
    int segundo = p + fen.query (p + 1);
    is_valid[p] = true;
 //   assert (primeiro < segundo);
    res += segundo - primeiro;
    if (s[i] < 0) --res;
    fen.range_update (p + 1, N, - 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