Cod sursa(job #966102)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 25 iunie 2013 12:56:01
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <iostream>
using namespace std;

#define init m = (l + r)/2, L = n << 1, R = L | 1
#define NMAX 201
 
int H[3 * NMAX];

inline void update (int n, int l, int r, int p, int v){
    if (l == r){H[n] += v; return;}
    int init;
    if (p <= m) update (L, l, m, p, v);
    else
        update (R, m + 1, r, p, v);
    H[n] = H[L] + H[R];
}
 
inline int query (int n, int l, int r, int i, int j){
    if (i <= l && r <= j) return H[n];
    int m = (l + r) / 2; int sol = 0;
    if (i <= m) sol = sol + query(2 * n, l, m, i, j);
    if (j > m) sol = sol + query(2 * n + 1, m + 1, r, i, j);
    return sol;
}

int i, N, ANS;
char s;

int main() {
	freopen("litere.in","r",stdin);
	freopen("litere.out","w",stdout);
	scanf("%i\n", &N);
	for (i = 1; i <= N; ++i) {
		scanf("%c", &s);
		update(1, 1, 201, (int) s, 1);
		ANS += query(1, 1, 201, (int) s + 1, 201);
	}
	printf("%i\n", ANS);
	return 0;
}