Cod sursa(job #3247694)

Utilizator paull122Paul Ion paull122 Data 8 octombrie 2024 20:09:38
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

#define VMAX 50000
#define NMAX 20000000

#define LOG 19
#define INF (long long)(1e9)
#define MOD 123457
#define ll long long int

#define ADD 1e9

#define NIL 0




using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");


int aib[27];
int n;
ll res;

void update(int p,int x)
{
    for(int i=p;i<=26;i+=i&-i)
    {
        aib[i] += x;
    }
}
int query(int x)
{
    int k=0;
    for(int i=x;i>=1;i-=i&-i)
    {
        k += aib[i];
    }
    return k;
}
int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        char x;
        fin >> x;
        x=x-'a'+1;
        update(x,1);
        res += i-query(x);
    }
    fout << res;
}