Apple Catching

Explicación

Para que una vaca atrape una manzana, debe llegar antes de que la manzana golpee la recta numérica. Sea el ítem $i$ la vaca y el ítem $j$ la manzana. Por tanto, para atrapar la manzana, debe cumplirse $|x_i - x_j| \le t_j - t_i$ . Después de extraer el valor absoluto, obtenemos estas dos desigualdades.

x_j - t_j \le x_i - t_i

x_i + t_i \le x_j + t_j

Representamos cada ítem como un punto $(x_i - t_i, x_i + t_i)$ . Según las desigualdades de arriba, para que una vaca atrape una manzana, el punto de la manzana debe estar a su arriba-izquierda. Así, podemos ordenar de forma creciente según $x_i - t_i$ y asignar de forma voraz manzanas con valores mayores de $x_i + t_i$ a cada vaca. Para maximizar la cantidad atrapada, debemos emparejar cada vaca con las manzanas de coordenada y más baja que aún cumplan las condiciones de arriba.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 2e5;
 
struct Item {
	int q;  // tipo (vaca o manzana)
	int t;  // tiempo de entrada
	int x;  // posición
	int n;  // cantidad
 
	bool operator<(const Item &y) {
		if (x - t == y.x - y.t) { return q > y.q; }
		return x - t < y.x - y.t;
	}
} p[MAX_N];
 
int main() {
	int N;
	map<int, int> pts;  // guarda cuántas manzanas hay en cada punto definido arriba
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> p[i].q >> p[i].t >> p[i].x >> p[i].n; }
 
	sort(p, p + N);
 
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (p[i].q == 2) {
			pts[p[i].x + p[i].t] += p[i].n;
		} else {
			int n = p[i].n;
			// asignar de forma voraz las vacas a los puntos más cercanos
			while (n) {
				map<int, int>::iterator it = pts.lower_bound(p[i].x + p[i].t);
 
				if (it == pts.end()) break;
				int u = min(n, it->second);
 
				if (u == it->second) {
					pts.erase(it);
				} else {
					it->second -= u;
				}
 
				n -= u;
				ans += u;
			}
		}
	}
 
	cout << ans << endl;
}