Forest density

#include <iostream>
#include <string>
#include <utility>
#include <vector>



struct Rect{
  int y1, x1, y2, x2;
};

std::vector<int> PrefixSum2D(int n, int*data){
  std::vector<int> sum((n+1)*(n+1), 0);

  for (int y=0;y<n;++y){
    for (int x=0;x<n;++x) {
      sum[(x+1) + (n+1) * (y+1)] = data[x + n * y];

      sum[(x+1) + (n+1) * (y+1)] += sum[(x+1) + (n+1) * y];
      sum[(x+1) + (n+1) * (y+1)] += sum[x + (n+1) * (y+1)];
      sum[(x+1) + (n+1) * (y+1)] -= sum[x + (n+1) * y];
    }
  }

  return sum;
}


int getRectSum(Rect r, int n, int* sum){
  int rectSum  = sum[(r.x2+1) + (n+1) * (r.y2+1)];
  rectSum     -= sum[r.x1     + (n+1) * (r.y2+1)];
  rectSum     -= sum[(r.x2+1) + (n+1) * r.y1];
  rectSum     += sum[r.x1     + (n+1) * r.y1];
  return rectSum;
}



int main(){
  int tn, m;
  std::cin >> tn >> m;
  int n = tn*tn;
  std::vector<int> vals(n);
  for (int i = 0; i<tn; ++i){
    std::string row;
    std::cin >> row;
    for (int j = 0; j<tn; ++j){
      const char c = row[j];
      int tree = (c=='*'); //1 if tree, 0 if empty
      vals[i*tn+j] = tree;
    }
  }

  std::vector<int> ps = PrefixSum2D(tn, vals.data());

  std::vector<Rect> queries(m);
  for (int q = 0; q<m; ++q){
    int y1,x1,y2,x2;
    std::cin >> y1 >> x1 >> y2 >> x2;
    queries[q].y1 = y1-1;
    queries[q].x1 = x1-1;
    queries[q].y2 = y2-1;
    queries[q].x2 = x2-1;
  }

  for (int q = 0; q<m; ++q){
    int sum = getRectSum(queries[q], tn, ps.data());
    std::cout << sum << "\n";
  }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED