Cod sursa(job #2712438)

Utilizator tomaionutIDorando tomaionut Data 25 februarie 2021 19:19:31
Problema Litere Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.5 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("grozavesti.in");
ofstream fout("grozavesti.out");
int n,x,sol,aib[200];
char ch;
void Update(int x)
{
	while (x <= 26)
	{
		aib[x]++;
		x += (x & (-x));
	}
}
int Query(int x)
{	
	int s = 0;
	while (x > 0)
	{
		s += aib[x];
		x -= (x & (-x));
	}
	return s;
}
int main()
{	
	fin >> n;
	for (int i = 0; i < n; i++)
	{
		fin >> ch;
		x = ch - 'a'+1;
		sol += i - Query(x);
		Update(x);
	}
	fout << sol;


	return 0;
}