Cod sursa(job #279361)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 12 martie 2009 19:54:22
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#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;
    }