Official Analysis (C++)

Explanation

We can maintain a $N$ by $N$ grid representing the beauty values of all the cows. We also maintain a 2D array $\text{sum}[i][j]$, which represents the attractiveness index of the $K$ by $K$ picture with its upper-left corner at $(i, j)$.

At each query, we update the attractiveness indices of all photos which contain the updated cow, as they will be the only photos affected. Updating the running maximum with these new values, we get the answer for the query.

This runs within the time limit because, for each query, $\text{sum}[i][j]$ is updated $\mathcal{O}(K^2)$ times, which is no more than 625 entries. Since these values only ever increase, we do not need to recompute the entire answer. Instead, we only need to account for the newly updated cells.

Implementation

Time Complexity: $\mathcal{O}(N^2 + QK^2)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, k, q;
	cin >> n >> k >> q;