Cod sursa(job #166977)

Utilizator VmanDuta Vlad Vman Data 28 martie 2008 19:43:56
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
//arbori indexati binar :P
#include <stdio.h>

#define alfa 27
#define bit(x) ( (x ^ (x-1)) & x )

int N,i,nr;
int A[alfa+1];
char c;

void update(int v)
{
 int i;
 for (i=v;i>0;i-=bit(i))
     ++A[i];
}

int query(int v)
{
 int i,s;
 for (i=v,s=0;i<=alfa;i+=bit(i))
     s+=A[i];
 return s;    
}

int main()
{
 freopen("litere.in","r",stdin);
 freopen("litere.out","w",stdout);
 scanf("%d\n",&N);
 while (N)
       {
        --N;
        scanf("%c",&c);
        nr+=query(c-'a'+1);
        update(c-'a');
       }
 printf("%d",nr);
 fclose(stdout);
 return 0;
}