Codeforces Codeforces Round #359 (Div. 1) - D. Kay and Eternity

Problem Statement:
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;
}