Cod sursa(job #116693)

Utilizator filipbFilip Cristian Buruiana filipb Data 19 decembrie 2007 12:41:06
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>
#include <string.h>

#define NMax 10005

int N, cnt, A[32];
char S[NMax];

int query(int x)
{
    int r;

    for (r = 0; x; x -= x^(x-1) & x)
        r += A[x];
    return r;
}

void update(int x)
{
    for (; x <= 26; x += x^(x-1) & x)
        A[x]++;
}

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

    scanf("%d %s", &N, &S);
    for (i = 0; i < N; i++)
    {
        cnt += query(26) - query(S[i]-'a'+1);
        update(S[i]-'a'+1);
    }

    printf("%d\n", cnt);

    return 0;
}