POI 2017 - Containers

Time Complexity: $\mathcal O((K + N) \sqrt N)$.

Let's consider two naive solutions and try to combine them! (In general, this is a good idea for square-root-decomposition problems.)

Naive solution 1 - slow update; fast query

Keep an array that stores the number of containers on each position. When we process a crane, we can simply increment the positions that it puts containers on.

Querying the final answer only takes $\mathcal O(N)$ time, but processing all of the cranes can potentially take $\mathcal O(KN)$ time in total.

This solution would work well if all $d_i$ were large, as processing each crane takes $\mathcal O(N / d_i)$ time.

Naive solution 2 - fast update; slow query

Let $dp[x][y]$ denote the prefix sum of the number of cranes with $d_i = y$ and $x \equiv a_i \pmod{y}$. When we process a crane, we change exactly two values in the DP array. The answer for position $p$ is simply

Processing all of the cranes now only takes only $\mathcal O(K)$ time, but querying the final answer can potentially take $\mathcal O(NK)$ time.

This solution would work well if all $d_i$ were small, as we querying the solution takes $\mathcal O(N \cdot \max(d_i))$ time.

Model solution - fast(ish) update; fast(ish) query

When $d_i \geq \sqrt N$, then apply solution 1. Otherwise, apply solution 2.

After processing all the cranes, we can simply add the results from the two solutions.

Copy
#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);