Archaeological Digs
Time limit1sMemory limit128 MB
Given repeated item coordinates on a small grid and a list of query cells, sum how many items fall in those cells.
- Level
Easy3 of 10
- Topics
- Hash map, Implementation
- Solved
- No attempts yet
Problem
Archaeologists at a dig divide the area they are examining into a grid and record which grid cell each item is found in. This makes it easy to tell how many items were found in a given cell.
For each scenario you are given the coordinates of the cells where items were found. For a list of query cells, determine the total number of items contained in those cells.
Input
The input consists of several scenarios.
The first line of each scenario contains two integers and , separated by a space, representing the length and width of the grid (). A scenario in which and are both marks the end of input.
The second line contains a single integer , the number of items located by the archaeologists (). This is followed by lines, each containing the and coordinates of the cell in which an item was found. The grid coordinate system starts at , and several items may be found in a single cell, so cell coordinates may be repeated.
After the item locations comes a list of cells for which the total number of found items is required. The first line of this section is a single integer , the number of cells (). It is followed by lines, each containing the and coordinates of a cell.
Output
Output a single line for each scenario. Each line contains the total number of items found in the listed cells.
Hint
In the example, cell contains items (it appears twice in the input list), cell contains , and cell contains none (it does not occur in the input list). The total is therefore .