Pagini recente » Cod sursa (job #2698455) | Cod sursa (job #1625623) | Cod sursa (job #3237070) | Cod sursa (job #2566016) | Cod sursa (job #279361)
Cod sursa(job #279361)
#include <fstream>
#include <string>
using namespace std;
int N,cnt[32];
string a,b;
int merge(int l,int r){
if (l==r) return 0;
int i,j,k,nr,m=(l+r)/2;
nr=merge(l,m)+merge(m+1,r);
for (i='a';i<='z';++i) cnt[i-'a']=0;
for (i=m+1;i<=r;++i) cnt[a[i]-'a']++;
for (i='b';i<='z';++i) cnt[i-'a']+=cnt[i-'a'-1];
for (i=l;i<=m;++i)
if (a[i]>'a') nr+=cnt[a[i]-'a'-1];
for (i=l,j=m+1,k=l;i<=m || j<=r;)
if ( j>r || (i<=m && a[i]<a[j]) )
b[k++]=a[i++];
else
b[k++]=a[j++];
for (i=l;i<=r;++i) a[i]=b[i];
return nr;
}
int main(){
ifstream f("litere.in");
ofstream g("litere.out");
f>>N;
getline(f,a);
getline(f,a);
b.resize(N);
g<<merge(0,N-1);
return 0;
}