Cod sursa(job #3205503)

Utilizator unomMirel Costel unom Data 19 februarie 2024 20:08:35
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>

using namespace std;

#define int long long

ifstream in("litere.in");
ofstream out("litere.out");
int n;
int v[10005];
int a[50];
string s;

void update(int p)
{
    for(int i = p; i<=26; i+=(i&-i))
    {
        a[i]++;
    }
}

int query(int p)
{
    int suma = 0;

    for(int i = p; i>=1; i-=(i&-i))
    {
        suma += a[i];
    }

    return suma;
}

signed main()
{
    in>>n;
    in>>s;

    for(int i = 0; i<n; i++)
    {
        v[i+1] = s[i] - 'a' + 1;
    }

    int ans = 0;
    for(int i = 1; i<=n; i++)
    {
        ans += (i - 1) - query(v[i]);

        update(v[i]);
    }

    out<<ans;

    return 0;
}