Pagini recente » Cod sursa (job #685377) | Cod sursa (job #1870505) | Cod sursa (job #630347) | Cod sursa (job #2621416) | Cod sursa (job #3172730)
#include <bits/stdc++.h>
using namespace std;
char a[100004],b[100004];
int m,n;
long long nr;
ifstream in("litere.in");
ofstream out("litere.out");
int Pivot(int st, int dr)
{
int i,p,j=st;
swap(a[st],a[(st+dr)/2]);
p=a[st];
for(i=st+1; i<=dr; i++)
if(a[i]<p)
{
j++;
swap(a[j],a[i]);
}
swap(a[st],a[j]);
return j;
}
int Q(int st, int dr)
{
int p=Pivot(st,dr);
if(p-st>1) Q(st,p-1);
if(dr-p>1) Q(p+1,dr);
}
void Intercl(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);
Intercl(st, m, dr);
}
}
int main()
{
int i;
in>>n;
for(i=1; i<=n; i++)
in>>a[i];
MergeSort(1,n);
out<<nr;
return 0;
}