Cod sursa(job #2069800)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 18 noiembrie 2017 20:31:43
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
# include <fstream>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
char ch;
int arb[27],f[27],n,i,sol;
void update(int poz){
    for(int i=poz;i<=26;i+=(i&(-i)))
        arb[i]++;
}
int query(int poz){
    int s=0;
    for(int i=poz-1;i>=1;i-=(i&(-i)))
        s+=arb[i];
    return s;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>ch;
        f[ch-'a'+1]++;
        update(ch-'a'+1);
        sol+=i-query(ch-'a'+1)-f[ch-'a'+1];
    }
    fout<<sol<<"\n";
    return 0;
}