Cod sursa(job #3348313)

Utilizator alexkAlexandru Kelemen alexk Data 20 martie 2026 18:03:10
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <string>
using namespace std;
ifstream cin("litere.in");
ofstream cout("litere.out");
const int nmax=1e4;
int n, f[30], spf[30], catelea[30], loc[30][nmax+5], sploc[30][nmax+5], nrbig[nmax+5];
long long int ans=0;
string s;
int main()
{
    cin>>n>>s;
    for(int i=0;i<n;i++)
        f[s[i]-'a']++, loc[s[i]-'a'][i]++;
    spf[0]=0;
    for(int i=1;i<26;i++)
        spf[i]=spf[i-1]+f[i-1];
    for(int i=0;i<26;i++)
    {
        for(int j=1;j<=n;j++)
            sploc[i][j]=sploc[i][j-1]+loc[i][j];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=(int)(s[i]-'a');j<26;j++)
        {
            nrbig[i]=nrbig[i]+(sploc[j][n]-sploc[j][i]);
        }
    }
    for(int i=0;i<n;i++)
    {
        catelea[s[i]-'a']++;
        /// dupa aranjarea lexi va fi pe spf[s[i]-'a']+catelea[s[i]-'a']
        int pozf=spf[s[i]-'a']+catelea[s[i]-'a'];
        /// inainte sa ajungem la el, unde va fi?
        /// va fi mai la nrbig[i] de sfarsit
        int pozi=n-nrbig[i];
        ans=ans+(pozi-pozf);
    }
    cout<<ans;
    return 0;
}