Cod sursa(job #190383)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 21 mai 2008 20:32:40
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <cstdio>
#include <cstring>

#define fin  "litere.in"
#define fout "litere.out"

#define lastb(x) ( x & ( ~ ( x - 1 ) ) )

const int Nmax = 10200;
const int Cmax = 27;

int N,sum[Cmax],cnt;
char buff[Nmax];

void insert(int p)
{
	int x;

	for ( x = p; x < Cmax; x += lastb(x) )
		++sum[x];
}

int query(int p)
{
	int x,ret = 0;

	for ( x = p; x > 0; x -= lastb(x) )
		ret += sum[x];
	return ret;
}

int main()
{
	int i;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	scanf("%d\n",&N);

	fgets(buff,Nmax,stdin);

	for ( i = 0; i < N; ++i )
	{
		insert(buff[i]-'a'+1);
		cnt += query('z'-'a'+1) - query(buff[i]-'a'+1);
	}

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

	return 0;
}