Containers

Complejidad temporal: $\mathcal O((K + N) \sqrt N)$.

Consideremos dos soluciones naive e intentemos combinarlas. (En general, esta es una buena idea para problemas de descomposición por raíz cuadrada.)

Solución naive 1 - actualización lenta; consulta rápida

Mantenemos un arreglo que guarda el número de contenedores en cada posición. Cuando procesamos una grúa, simplemente incrementamos las posiciones en las que coloca contenedores.

Consultar la respuesta final solo toma $\mathcal O(N)$ de tiempo, pero procesar todas las grúas puede tomar potencialmente $\mathcal O(KN)$ de tiempo en total.

Esta solución funcionaría bien si todos los $d_i$ fueran grandes, ya que procesar cada grúa toma $\mathcal O(N / d_i)$ de tiempo.

Solución naive 2 - actualización rápida; consulta lenta

Sea $dp[x][y]$ la suma de prefijos del número de grúas con $d_i = y$ y $x \equiv a_i \pmod{y}$. Cuando procesamos una grúa, cambiamos exactamente dos valores en el arreglo de DP. La respuesta para la posición $p$ es simplemente

Procesar todas las grúas ahora solo toma $\mathcal O(K)$ de tiempo, pero consultar la respuesta final puede tomar potencialmente $\mathcal O(NK)$ de tiempo.

Esta solución funcionaría bien si todos los $d_i$ fueran pequeños, ya que consultar la solución toma $\mathcal O(N \cdot \max(d_i))$ de tiempo.

Solución modelo - actualización (más o menos) rápida; consulta (más o menos) rápida

Cuando $d_i \geq \sqrt N$, aplicamos la solución 1. En caso contrario, aplicamos la solución 2.

Después de procesar todas las grúas, simplemente sumamos los resultados de las dos soluciones.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
 
const int sqrt_n = 300;
int containers[100001];
int dp[100001 + sqrt_n][sqrt_n];
 
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	while (k--) {
		int a, l, d;
		cin >> a >> l >> d;
		if (d >= sqrt_n) FOR(i, 0, l) containers[a + i * d]++;
		else {
			dp[a][d]++;
			dp[a + (l * d)][d]--;
		}
	}
 
	FOR(j, 1, sqrt_n) FOR(i, j, n + 1) dp[i][j] += dp[i - j][j];
 
	FOR(i, 1, n + 1) {
		FOR(j, 1, sqrt_n) containers[i] += dp[i][j];
		cout << containers[i] << ' ';
	}
}