Cod sursa(job #1428401)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 4 mai 2015 14:42:18
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
/*
    Worg
*/
#include <cstdio>

#define DIM 10010
#define zeros(x) ((x ^ (x - 1)) & x)
#define sigma 27
#define I64 long long int
#define val(x) x - 'a' + 1

using namespace std;
FILE *fin=freopen("litere.in","r",stdin);
FILE *fout=freopen("litere.out","w",stdout);

char S[DIM];
int AIB[sigma + 1];
int len;

inline void Add(int pos, int val)
{
    int i;
    for(i = pos; i <= sigma; i += zeros(i))
        AIB[i] += val;
}

inline int Query(int pos)
{
    int i, ret = 0;
    for(i = pos; i; i -= zeros(i))
        ret += AIB[i];
    return ret;
}

int main()
{
    int i;
    I64 ans = 0;

    scanf("%d ", &len);
    gets(S);
    for(i = 0; i < len; ++i)
    {
        ans += 1LL * Query( sigma ) - 1LL * Query( val( S[i] ) );
        Add( val( S[i] ), 1 );
   }
   printf("%lld", ans);
}