The Timber Auction

All submissions for this problem are available.
The GoC Timber Mafia is notorious for its deforestation activities in the forests near Siruseri. These activities have increased multifold after the death of the bandit who used to lord over these jungles. Having lost the battle to prevent the Mafia from illegally felling the teak trees in this forest, the government of Siruseri came up with a novel idea. Why not legalise the deforestation activity and at least make some money in the process? So the Government decided to lease out parts of the forest to the Timber Mafia. Most of the teak trees in the forests of Siruseri were planted during the colonial times, after the native trees had been cut. Like everything European, the forest is very regular and orderly. It is rectangular in shape and the trees are arranged in uniformly spaced rows and coloumns. Since the trees differ in height and girth, the timber value differs from tree to tree. The forest department has collected data on each tree and knows the volume of wood (in cubic feet) available in each tree in the forest. The forest department maintains this information in the form of an $M \times N$ array of integers, where the $(i, j)$th entry is the volume, in cubic feet, of the $i^{th}$ tree on the $i^{th}$ row (or, equivalently, the $i^{th}$ tree on the $i^{th}$ column). We assume that our rows are numbered top to bottom and the columns are numbered from left to right. For example, such an array could look like ![11](https://i.imgur.com/u16DWIQ.png "Figure 1") This array tells us that the volume of the tree at position $(3,4)$ is $15$ cubic feet and so on. Any rectangular piece of land with trees at each corner can be leased out. In order to fix the lease price for any rectangular plot of the forest the forest department needs to know the amount of wood available inside the plot. A rectangular plot is described by the positions of the trees in its top left corner and the bottom right corner. For example the positions $(2,2)$ and $(3,4)$ describes the following part rectangular part of the above forest. ![11](https://i.imgur.com/TUPVGg7.png "Figure 2") The total amount of wood available in this rectangular plot is $76$ cubic feet. Similarly $(4,2)$ and $(4,2)$ describes the rectangle with just one tree and its volume is $20$ cubic feet. Your task is to write a program that helps the forest department to compute the total volume of the trees insides any specfied rectangular plot. ###Input:  The first line of the input contains two integers $M$ and $N$ indicating the number of rows and columns of trees in the forest.  The following $M$ lines have $N$ integers each. The $j^{th}$ integer on line $i+1$ denotes the volume (in cubic feet) of the $j^{th}$ tree on the $i^{th}$ row.  Line $M+2$ contains a single integer $C$ indicating the number of rectangles for which the total volume is to be computed.  Each of the following $C$ lines (line $M+2+1 ... M+2+C$) contain four integers $x_1, y_1, x_2$ and $y_2$ (with $x_1 \leq x_2$ and $y_1 \leq y_2$) and describes a rectangle. The rectangle has its top left corner at the tree in position $(x_1,y_1)$ and its bottom right corner at the tree at position $(x_2,y_2)$. ###Output: Your output must contain $C$ lines with one integer on each line. Line $i$ must contain the total volume of wood in the rectangle described on line $M+2+i$ in the input. ###Constraints  In $30 \%$ of inputs, $1 \leq C \leq 100$.  In all inputs, $2 \leq N, M \leq 1000$ and $1 \leq C \leq 1000000$  $0 \leq$ volume of wood in each tree $\leq 1000$  $1 \leq x_1 \leq x_2 \leq M$  $1 \leq y_1 \leq y_2 \leq N$ ###Sample Input 4 4 3 4 15 23 14 20 12 9 3 8 12 15 12 20 7 5 2 2 2 3 4 4 2 4 2 ###Sample Output 76 20Author:  deepcpp 
Date Added:  1092018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions