Pagini recente » Monitorul de evaluare | Cod sursa (job #1890930) | Diferente pentru home intre reviziile 225 si 226 | Cod sursa (job #117563) | Cod sursa (job #1574985)
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
ofstream g("litere.out");
int AIB[10005], Index[10005], V[10005];
int n, pos;
char Buffer[100000];
void citeste_numar(int & nr)
{
nr = 0;
while(Buffer[pos] < '0' || Buffer[pos] > '9')
pos++;
while(Buffer[pos] >= '0' && Buffer[pos] <= '9')
nr = nr*10 + Buffer[pos++] - '0';
}
void citeste_litera(int & nr)
{
nr = 0;
while(Buffer[pos] < 'a' || Buffer[pos] > 'z')
pos++;
nr = Buffer[pos++] - 'a' + 1;
}
void citire()
{
freopen("litere.in", "r", stdin);
fread(Buffer, 1, 100000, stdin);
citeste_numar(n);
for(int i=1; i<=n; i++){
citeste_litera(V[i]);
}
}
bool comp(int x, int y)
{
if(V[x] != V[y])
return V[x] < V[y];
return x < y;
}
void Update(int poz)
{
while(poz <= n){
AIB[poz]++;
poz += poz&(-poz);
}
}
int Query(int poz)
{
int sum = 0;
while(poz > 0){
sum += AIB[poz];
poz -= poz&(-poz);
}
return sum;
}
void rez()
{
int i, nrmut = 0;
for(i=1; i<=n; i++)
Index[i] = i;
sort(Index + 1, Index + n + 1, comp);
for(i=1; i<=n; i++){
nrmut += Index[i] - Query(Index[i]) - 1;
Update(Index[i]);
}
g<<nrmut<<"\n";
}
int main()
{
citire();
rez();
return 0;
}