All submissions for this problem are available.
You are given an array of M*N elements each with non-negative value. Now you will be given query denoted by 2 cordinates which will denote the top-left point of a sub-rectangle and bottom-right point of the sub-rectangle. Now you need to find the sum of all the elements in the given sub-rectangle.
The first line of the input contains two integers M and N indicating the number of rows and columns.The following M lines have N integers each which denotes the value at that particular cell.Line M+2 contains a single integer C indicating the number of sub-rectangles for which the total sum needs to be computed. Each of the following C lines (line M+2+1 ... M+2+C) each contain four integers x1, y1, x2 and y2 (with x1 ≤ x2 and y1 ≤ y2) and describes a rectangle. The rectangle has its top left corner at the tree in position (x1,y1) and its bottom right corner at the tree at position (x2,y2).
Your output must contain C lines with one integer on each line. Line i must contain the total sum n the rectangle described on line M+2+i in the input.
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 Output: 76 20
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.