Cod sursa(job #658217)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 8 ianuarie 2012 13:39:28
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#define NMAX 500001
#include <cstring>
#include <algorithm>

using namespace std;

ifstream f("litere.in");
ofstream g("litere.out");

struct sr {
    long long v;
    int p;
};
sr a[200005];
int n,i,x,val,inv,b[200005];
int Arb[NMAX];
string input;

void update(int poz,int val) {
    int p,k;
    while (poz<=n) {
        Arb[poz]+=val;p=1;k=0;
        while ((poz&p)==0) {
            k++;
            p<<=1;
        }
        poz+=(1<<k);
    }
}
int query(int poz) {
    int p,k,val=0;
    while (poz>0) {
        val+=Arb[poz];p=1;k=0;
        while ((poz&p)==0) {
            k++;
            p<<=1;
        }
        poz-=(1<<k);
    }
    return val;
}

bool comp (sr t,sr l) {
    if (t.v!=l.v) return t.v<l.v;
    return t.p<l.p;
}

int main() {
    memset(Arb,0,sizeof(Arb));
    f >> n;f.get();
    getline(f,input);
    for (i=1;i<=n;i++) {
         a[i].v=int(input[i-1])-int('a')+1;a[i].p=i;
    }
    sort(a+1,a+n+1,comp);
    for (i=1;i<=n;i++) b[a[i].p]=i;
    for (i=1;i<=n;i++) {
         x=b[i];
         inv=(inv+query(n)-query(x));
         update(x,1);
    }
    g << inv << '\n';
    f.close();g.close();
    return 0;
}