Cod sursa(job #2782748)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 12 octombrie 2021 22:20:59
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("litere.in");
ofstream fout("litere.out");

const int MAXN = 1e4;
int n, aib[1 + MAXN];
deque<int> dq[26];

void update(int x, int t) {
  for (int i = ++x; i <= n; i += i & -i) {
    aib[i] += t;
  }
}

int query(int x) {
  int ans = 0;
  for (int i = x; i >= 1; i -= i & -i) {
    ans += aib[i];
  }
  return ans;
}

void test_case() {
  string s, t;
  fin >> n >> s;
  t = s;
  sort(t.begin(), t.end());
  for (int i = 0; i <= n - 1; ++i) {
    dq[t[i] - 'a'].emplace_back(i);
  }
  int ans = 0;
  for (int i = 0; i <= n - 1; ++i) {
    int x = dq[s[i] - 'a'].front();
    dq[s[i] - 'a'].pop_front();
    ans += i - query(x);
    update(x, 1);
  }
  fout << ans << '\n';
}

int main() {
  int t = 1;
  for (int tc = 1; tc <= t; ++tc) {
    test_case();
  }
  return 0;
}