Submission #515039

#	Time	Username	Problem	Language	Result	Execution time	Memory
515039		MilosMilutinovic	Ekoeko (COCI21_ekoeko)	C++14	110 / 110	13 ms	3692 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  n = 2 * n;
  vector<vector<int>> pos(26);
  for (int i = 0; i < n; i++) {
    pos[s[i] - 'a'].push_back(i);
  }
  vector<int> cnt(26);
  for (int i = 0; i < 26; i++) {
    cnt[i] = (int) pos[i].size() / 2;
  }
  string t = "";
  for (int i = 0; i < n; i++) {
    int c = s[i] - 'a';
    if (cnt[c] > 0) {
      t += s[i];
      cnt[c] -= 1;
    }
  }
  t = t + t;
  vector<int> a;
  vector<int> nxt(26);
  for (int i = 0; i < n; i++) {
    int c = t[i] - 'a';
    a.push_back(pos[c][nxt[c]]);
    nxt[c] += 1;
  }
  long long ans = 0;
  fenwick<int> fenw(n);
  for (int i = 0; i < n; i++) {
    ans += i - fenw.get(a[i]);
    fenw.modify(a[i], 1);
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40