Cod sursa(job #2069800)
Utilizator | 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;
}