Cod sursa(job #2712440)
Utilizator | Data | 25 februarie 2021 19:20:06 | |
---|---|---|---|
Problema | Litere | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
int n,x,sol,aib[200];
char ch;
void Update(int x)
{
while (x <= 26)
{
aib[x]++;
x += (x & (-x));
}
}
int Query(int x)
{
int s = 0;
while (x > 0)
{
s += aib[x];
x -= (x & (-x));
}
return s;
}
int main()
{
fin >> n;
for (int i = 0; i < n; i++)
{
fin >> ch;
x = ch - 'a'+1;
sol += i - Query(x);
Update(x);
}
fout << sol;
return 0;
}