Editor

Orchard Survey

#636 · Grids and matrices · Advanced · Fast enough · 145 XP · about 30 min

An orchard is planted on a grid. grid is a list of rows, and grid[r][c] is 1 if a tree grows at row r, column c, and 0 if the spot is empty. A buyer wants to know how many trees are in each of many rectangular plots. A plot is a tuple (top, left, bottom, right): it covers rows top to bottom and columns left to right, edges included.

Write trees_in_plots(grid, plots) that returns a list with the number of trees in each plot, in order.

Examples

grid = [
    [1, 0, 1],
    [0, 1, 1],
    [1, 1, 0],
]
trees_in_plots(grid, [(0, 0, 2, 2), (1, 1, 2, 2), (0, 2, 0, 2)])
# returns [6, 3, 1]

The first plot is the whole orchard, the second is the two by two square at the bottom right, and the third is the single spot at row 0, column 2.

Constraints

  • The grid has 1 to 800 rows and 1 to 800 columns, and every row has the same length.
  • 0 <= len(plots) <= 100,000
  • 0 <= top <= bottom < rows and 0 <= left <= right < columns

Time limit

Each test must finish within 10 seconds, and the hidden tests ask about 100,000 plots of an 800 by 800 orchard.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.