Cod sursa(job #123247)

Utilizator blasterzMircea Dima blasterz Data 15 ianuarie 2008 09:16:42
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>
#define bit(x) ( (x) &( ((x)-1) ^(x)) )
#define maxn 10001
int H[maxn];
char a[maxn];
int n;

inline void update(int x, int v)
{
   for(int i=x; i<=256; i+=bit(i)) H[i]+=v;
}

inline int query(int x)
{
   int s=0;
   for(int i=x; i>0; i-=bit(i)) s+=H[i];
   return s;
}

void read()
{
   freopen("litere.in","r",stdin);
   scanf("%d\n", &n);
   int i;
   gets(a);
   //for(i=0;i<n;++i) update(a[i]);
}

int main()
{
   int i,sol=0;
   read();
    for(i=0;i<n;++i) update(a[i],1);

     for(i=0;i<n-1;++i)
    {
      update(a[i], -1);
      sol+=query(a[i]-1);
     }

    freopen("litere.out","w",stdout);
    printf("%d\n", sol);
    return 0;
}