Forest density

#include <bits/stdc++.h>

using namespace std;

//Definitions for quicker writing
#define REP(i,c,d) for (int i = c; i < d; i++)

//Typedefs for quicker writing
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


int main() {
	//IO optimization
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//Input definition
	int n;
	int q;

	cin >> n >> q;

	//Initialize segment tree
	//int forest[n][n];
	int sum[n+1][n+1];
	sum[0][0] = 0;
	sum[0][1] = 0;
	sum[1][0] = 0;

	char val;
	REP(i,0,n){
		REP(j,0,n){
			cin >> val;
			if(val == '.'){
				sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j];
			}
			else{
				sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + 1;
			}
		}
	}

	
	//REP(i,0,2*n){
	//	cout << seg[i] << "\n";
	//}

	int y1;
	int x1;
	int y2;
	int x2;

	int res[q];

	REP(i,0,q){
		cin >> y1;
		cin >> x1;
		cin >> y2;
		cin >> x2;


		res[i] = sum[y2][x2] - sum[y2][x1-1] - sum[y1-1][x2] + sum[y1-1][x1-1];
	}
	

	//Write out
	REP(i,0,q){
		cout << res[i] << "\n";
	}	

	//Return
	return 0;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED