2007 - Sails

Pista 1

Consideremos el número de celdas en cada altura. Si $x$ es el número de celdas en una altura dada, entonces este nivel contribuye $\frac{x(x - 1)}{2}$ de ineficiencia al barco. Por esto, el orden en que ordenamos los mástiles no importa. ¿En qué orden deberíamos procesarlos?

Pista 2

Si procesamos los mástiles en orden creciente de altura, entonces para cada mástil podemos elegir los $k$ niveles dentro de la altura permitida que ya tienen la menor cantidad de velas, y agregar estas velas a esos niveles. ¿Cómo podemos realizar esta operación de forma eficiente?

Explicación

Como se mencionó en las pistas, procesamos cada mástil en orden ordenado. Podemos mantener un Árbol de Fenwick (BIT) que guarda el número de velas en cada nivel en orden descendente. Colocamos todas las velas en el rango $[h[i] - k[i] + 1, h[i]]$ (en el BIT), porque eso es óptimo. Para manejar colocar una vela en cada índice del rango, usamos la idea del arreglo de diferencias sobre nuestro BIT.

Sin embargo, aplicar esta adición de rango puede hacer que los valores del BIT dejen de estar ordenados en orden descendente. Supongamos que, después de aplicar todas las actualizaciones, los valores del BIT son los siguientes:

[5, 5, 4, 3, 1]

Si hacemos de forma directa una adición de rango sobre los últimos cuatro elementos, los valores resultantes serán:

[5, 6, 5, 4, 2]

Para remediar este problema, partimos la adición de rango en dos actualizaciones separadas. En el caso de arriba, podemos partir la adición de rango anterior en actualizaciones sobre el rango $[1, 1]$ y $[3, 5]$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\log^2N)$

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// BeginCodeSnip{Binary Indexed Tree (from the module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
	vector<int> h(n), k(n);
	for (int i = 0; i < n; i++) { cin >> h[i] >> k[i]; }
 
	vector<int> ord(n);
	iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int i, int j) -> bool { return h[i] < h[j]; });
 
	const int max_h = *max_element(begin(h), end(h));
	BIT<int> bit(max_h + 1);
 
	/** @return first index with bit.pref_sum(i) < val */
	const auto first_val = [&](int val, int high) {
		int low = 0;
		while (low < high) {
			int mid = low + (high - low) / 2;
			int cur_val = bit.pref_sum(mid);
			(cur_val < val) ? high = mid : low = mid + 1;
		}
		return low;
	};
 
	for (int i : ord) {
		int last = h[i] - k[i];
		int val = bit.pref_sum(last);
		int idx_1 = first_val(val, h[i]);
		int idx_2 = first_val(val + 1, h[i]);
		bit.add(idx_1, 1);
		bit.add(h[i], -1);
		bit.add(idx_2, 1);
		bit.add(idx_2 + k[i] - (h[i] - idx_1), -1);
	}
 
	ll res = 0;
	for (int i = 0; i < max_h; i++) {
		int sail_num = bit.pref_sum(i);
		res += 1ll * sail_num * (sail_num - 1) / 2;
	}
 
	cout << res << endl;
}