Cod sursa(job #464073)

Utilizator darrenRares Buhai darren Data 18 iunie 2010 16:55:50
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<cstring>
#include<fstream>
using namespace std;

int n, aib[32], inv;
char txt[10001];

void update(int p)
{
	for (; p <= 30; p += p & -p)
		++aib[p];
}

int query(int p)
{
	if (p == 0) return 0;
	int sum = 0;
	for (; p >= 1; p -= p & -p)
		sum += aib[p];
	return sum;
}

int main()
{
	ifstream fin("litere.in");
	ofstream fout("litere.out");
	fin >> n >> txt;
	for (int i = 0; i < n; ++i)
	{
		txt[i] -= 'a', ++txt[i];
		
		inv += query(30) - query(txt[i]);
		update(txt[i]);
	}
	fout << inv;
}