Pagini recente » Cod sursa (job #938911) | Cod sursa (job #333153) | Cod sursa (job #3265122) | Cod sursa (job #1959808) | Cod sursa (job #3172911)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
int a[100004],b[100004], m,n;
long long nr;
char ch;
void Intercls(int st, int m, int dr)
{
int i, j, k;
k = st;
i = st; j = m+1;
while (i <= m && j <= dr)
if (a[i] > a[j])
{
b[k++] = a[j++];
nr+=(m-i+1);
}
else b[k++] = a[i++];
while (i <= m) b[k++] = a[i++];
while (j <= dr) b[k++] = a[j++];
for (i = st; i <= dr; i++)
a[i] = b[i];
}
void Mergesort(int st, int dr)
{
if (dr - st >= 1)
{
int m = (st + dr) / 2;
Mergesort(st, m);
Mergesort(m+1, dr);
Intercls(st, m, dr);
}
}
int main()
{
int i;
fin>>n;
for(i=1; i<=n; i++)
{
fin>>ch;
a[i]=(int)ch;
}
Mergesort(1,n);
fout<<nr;
return 0;
}