Balanced Photo

La solución oficial usa un Árbol de Fenwick (BIT).

Una solución alternativa usa un árbol de estadísticas de orden. Esto se proporciona en C++ con la estructura de datos PBDS; en Java hay que implementar el propio.

Solución (solo C++)

Complejidad temporal: $\mathcal O(N \log N)$

Queremos determinar rápidamente, para cada vaca, la cantidad de vacas más altas a su izquierda y a su derecha.

Para esto, podemos barrer las vacas de izquierda a derecha y mantener dos árboles binarios de búsqueda balanceados: uno para almacenar las alturas de las vacas de cada lado de la vaca actual. Luego, usamos búsqueda binaria para contar la cantidad de alturas en cada conjunto que son mayores que la altura de la vaca actual.

Podemos usar árboles de estadísticas de orden para lograrlo en tiempo $\mathcal O(N \log N)$ .

C++


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  // para estructuras de datos basadas en políticas
using namespace __gnu_pbds;               // para estructuras de datos basadas en políticas
using namespace std;
 
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;  // indexed_set -> order_of_key & find_by_order
int N, h, ans;
vector<int> height;
indexed_set cow;  // almacenar altura de las vacas a la derecha
indexed_set woc;  // almacenar altura de las vacas a la izquierda
int main() {
	FILE *in, *out;
	in = fopen("bphoto.in", "r");
	out = fopen("bphoto.out", "w");
	fscanf(in, "%d", &N);
	for (int i = 0; i < N; i++) {
		fscanf(in, "%d", &h);
		cow.insert(h);
		height.push_back(h);
	}
	for (int i : height) {
		cow.erase(i);  // quitar la vaca actual de la derecha
		int le = woc.size() -
		         woc.order_of_key(i);  // order_of_key cuenta la cantidad de elementos
		                               // en el conjunto que son estrictamente menores que i
		int ri = cow.size() - cow.order_of_key(i);  // queremos contar la cantidad de
		                                            // elementos que son mayores que i
		woc.insert(i);                              // agregar la vaca actual a la izquierda
		if (max(le, ri) > 2 * min(le, ri)) ans++;
	}
	fprintf(out, "%d\n", ans);
}