http://codeforces.com/contest/685/problem/D

Summary:

In an infinite 2D array, there are n < 10^5 cells (x[i], y[i]) with value 1, where -1e9 <= x[i], y[i] <= 1e9. The rest of the cells are 0. For each m = 1 to n, compute the number of squares with dimension k x k (k <= 300), with the property that each of those squares has exactly m non-zero cells in it.

Solution:

Let's uniquely define a square as the index (i, j) of its left bottom corner. Imagine that we have a 2D array S such that S[i][j] is the number of non-empty cell in the square (i, j). One way to compute S is as follows: for each non-empty cell (x, y), add 1 to every S[s][t] such that s is in [x-k+1, x] and t is in [y-k+1, y].

Now the strategy is to make the above operation fast enough. Let's suppose that we have another array freq[s][t] which is initially 0 for all entries. Instead of adding 1 to every S[s][t] in those ranges, we can add 1 to the row x-k+1 in freq for column in range [y-k+1, y], and subtract 1 from the row x+1 in F from column [y-k+1, y]. S is then can be viewed as the cumulative frequency of freq along the column, i.e. S[s][t] = freq[s][t] + freq[s-1][t] + freq[s-2][t] + ... . Hence using this technique, we can transform all (x, y) cells into two queries of the form (row, L, R, val): (x-k+1, y-k+1, y, +1) and (x+1, y-k+1, y, -1) where (row, L, R, val) means perform addition of val to entries in freq[row][L ... R].

With the concept of cumulative frequency and transformation of the problem space into update queries, we can solve the problem as follows:

1) We will perform a sweeping line over all queries (row, L, R, val) in increasing row.

2) Firstly initialise two arrays last_updated[] and cnt[], where last_updated[i] stores the row of the latest update query performed on column i, while cnt[i] stores the value freq[last_updated[i]][i], the most current frequency value of column i. Also initialise ans[i] which will contain the total number of squares containing i non-empty cells.

3) For each query (row, L, R, val):

Iterate through i = L to R, update ans[cnt[i]] by adding row - last_updated[i] (because all values in S[row-1] to S[last_updated[i]] are equal to cnt[i]). Then update last_updated[i] = row, and update cnt[i] = cnt[i] + val.

Since we need to sort the queries in increasing row order, and for each query we need to iterate through k values, overall we need O(n log n + nk) time. Furthermore we need O(nk) space to store the corresponding cnt[] and last_updated[] of all possible column ranges that contains at least a valid square.

Below is the implementation of the above solution. (Note that the shrink_to_fit call is needed to pass the memory limit of this problem...)

Implementation:

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <utility> using namespace std; constexpr int N = 100001; constexpr int K = 301; struct Query { int row; int left; int right; bool val; bool operator<(const Query& other) const { if (row == other.row) { return left == other.left ? right < other.right : left < other.left; } return row < other.row; } }; constexpr int MIN_INF = (int) -1e9 - 7; int n, k; vector<int> last_updated; vector<int> cnt; vector<int> arr; vector<int64_t> ans; vector<Query> queries; int getIndex(int val) { int lo=0, hi=arr.size()-1, mid; while(lo<=hi){ mid = (lo+hi)/2; if (arr[mid] < val) { lo = mid+1; } else { hi = mid-1; } } return lo; } int main(){ int x,y; scanf("%d%d",&n,&k); vector<pair<int,int>> points; for (int i=0;i<n;++i){ scanf("%d%d",&x,&y); points.push_back({x,y}); } for (int i=0;i<n;++i){ for (int j=0;j<k;++j){ arr.push_back(points[i].second-k+j+1); } } points.clear(); sort(arr.begin(), arr.end()); int j=0; for (int i=1;i<arr.size();++i){ if (arr[j] == arr[i]) continue; arr[++j] = arr[i]; } arr.resize(j+1); for (int i=0;i<n;++i){ int left = getIndex(points[i].second-k+1); int right = getIndex(points[i].second); queries.push_back({points[i].first-k+1, left, right, true}); queries.push_back({points[i].first+1, left, right, false}); } sort(queries.begin(), queries.end()); arr.clear(); arr.shrink_to_fit(); ans.resize(n+1, 0); cnt.resize(j+1, 0); last_updated.resize(j+1, MIN_INF); for (int q=0;q<2*n;++q) { for (int i=queries[q].left; i <= queries[q].right; ++i){ ans[cnt[i]] += queries[q].row - last_updated[i]; last_updated[i] = queries[q].row; cnt[i] += queries[q].val ? 1 : -1; } } for(int i=1;i<=n;++i){ cout << ans[i] << " "; } cout << endl; return 0; }