Cod sursa(job #2142466)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 25 februarie 2018 01:33:43
Problema Litere Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>

#define NMAX 10000
#define TIPMAX 27

using namespace std;

int aib [ TIPMAX ] ;
int v [ NMAX ] ;

void update (int poz, int val ) {
  aib[poz] = val ;
  for (int i = poz ; i > 0 ; i -= i & (-i) )
    aib[i] += val ;
}

int query (int poz ) {
  int answer = 0 ;
  for (int i = poz ; i > 0 ; i -= i & (-i) )
    answer += aib[i] ;
  return answer ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("litere.in", "r" ) ;
  fout = fopen ("litere.out", "w" ) ;

  int n, i, s ;
  char c ;

  fscanf (fin, "%d\n", &n ) ;

  for (i = 1 ; i <= n ; i++ ) {
    c = fgetc(fin) ;
    v[i] = (c - 'a' ) + 1;
  }

  s = 0 ;
  for (i = 1 ; i <= n ; i++ ) {
    update (v[i], 1 ) ;
    s += ( query (v[i]) - query (TIPMAX-1) ) ;
  }

  fprintf (fout, "%d", s ) ;
  return 0;
}