Cod sursa(job #1541618)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 4 decembrie 2015 14:19:58
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>

const int MAX_N = 10000;
const int SIGMA = 26;

int fen[SIGMA];
char s[MAX_N + 1];

void updateFen(int indx) {
  for (; indx < SIGMA; indx |= (indx + 1)) {
      fen[indx]++;
  }
}

int queryFen(int indx) {
  int s = 0;
  for (; indx >= 0; indx = (indx & (indx + 1)) - 1) {
    s += fen[indx];
  }
  return s;
}

int main(void) {
  freopen("litere.in", "r", stdin);
  freopen("litere.out", "w", stdout);
  int n, q;

  scanf("%d\n", &n);
  gets(s);
  fclose(stdin);

  q = 0;
  for (int i = n - 1; i >= 0; i--) {
    q += queryFen(s[i] - 'a' - 1);
    updateFen(s[i] - 'a');
  }
  printf("%d\n", q);
  fclose(stdout);
  return 0;
}