Cod sursa(job #196926)

Utilizator gcosminGheorghe Cosmin gcosmin Data 30 iunie 2008 12:13:34
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <vector>
using namespace std;

int N;

vector <int> poz[30];

int aib[10010];

inline int lsb(int x) { return (x & (x - 1) ^ x); }

void update(int x)
{
	while (x) {
		aib[x]++;
		x -= lsb(x);
	}
}

int query(int x)
{
	int rez = 0;
	while (x <= N) {
		rez += aib[x];
		x += lsb(x);
	}

	return rez;
}

int main()
{
	int i;
	char c;

	freopen("litere.in", "r", stdin);
	freopen("litere.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; i++) {
		scanf(" %c", &c);

		poz[c - 'a'].push_back(i);
	}

	int pc = 0, rez = 0, q;
	for (i = 0; i < 26; i++) {
		for (vector <int> :: iterator it = poz[i].begin(); it != poz[i].end(); ++it) {
			pc++;
			q = query(*it);
			rez += *it + q - pc;
			update(*it);
		}
	}

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

return 0;
}