Skip to Content
CTRL K

Cow Jog

Análisis oficial (C++) 

Explicación

Se nos pide calcular la cantidad mínima de carriles (subsecuencias crecientes más largas), de modo que ninguna vaca se solape mientras corre.

Como la entrada ya está ordenada por pp, notemos que si dos vacas tienen pi+T⋅si≥pi+1+T⋅si+1p_{i}+T \cdot s_{i} \geq p_{i+1}+T \cdot s_{i+1}, entonces necesariamente se adelantaron en el camino.

Queremos asegurar lo contrario dentro de cada carril: pi+T⋅si<pi+1+T⋅si+1p_{i}+T \cdot s_{i} < p_{i+1}+T \cdot s_{i+1}, así que calculamos la cantidad mínima de subsecuencias estrictamente crecientes más largas de p+T⋅sp+T \cdot s. Esto es equivalente a la longitud de la subsecuencia no creciente más larga, como se menciona en el módulo.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("cowjog.in", "r", stdin);
	freopen("cowjog.out", "w", stdout);
 
	int n, t;
	cin >> n >> t;
	vector<long long> lds;
 
	// encontrar la cantidad mínima de subsecuencias estrictamente crecientes
	for (int i = 0; i < n; ++i) {
		long long pos, spd;
		cin >> pos >> spd;
		pos += spd * t;
		auto it = upper_bound(lds.begin(), lds.end(), pos, greater{});
		if (it == lds.end()) {
			lds.push_back(pos);
		} else {
			*it = pos;
		}
	}
 
	cout << lds.size() << '\n';
}
Fundamentos