Forest density

#include <bits/stdc++.h>

using namespace std;

#define bit(x, i) (x & (1 << i))  // select the bit of position i of x
#define lowbit(x) ((x) & ((x) ^ ((x) - 1)))  // get the lowest bit of x
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define BR "\n"
#define ALL(x) (x).begin(), (x).end()
#define IN(i, l, r) (l < i && i < r)
#define LINR(i, l, r) (l <= i && i <= r)
#define LIN(i, l, r) (l <= i && i < r)
#define INR(i, l, r) (l < i && i <= r)
#define REMAX(a, b) (a) = max((a), (b))
#define REMIN(a, b) (a) = min((a), (b));

// maps, pairs
#define mp make_pair
#define fi first
#define se second

// vectors
#define pb push_back
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;

using ll = long long;

const int INF = 1000000000;

int main() {
  // uncomment if io is a bottleneck
  // ios::sync_with_stdio(0);
  // cin.tie(0);

  // uncomment to read cin from a file
  // freopen("forest-density.txt", "r", stdin);

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

  int s[(n + 1)][(n + 1)] = {};
  REP(i, 1, n + 1) {
    REP(j, 1, n + 1) {
      char tile;
      cin >> tile;
      s[i][j] += (tile == '*') ? 1 : 0;
      s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
  }

  REP(i, 0, q) {
    int x1, y1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    int sum = s[y2][x2] - s[y2][x1 - 1] - s[y1 - 1][x2] + s[y1 - 1][x1 - 1];
    cout << sum << BR;
  }

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED