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