P2468 [SDOI2010] Susu's Bookshelf

Susu from Class B29 of Xingfu Kindergarten is a smart, obedient, and adorable child. Her hobbies are drawing and reading, and she especially likes the articles by Thomas H. Cormen. Susu’s home has a giant bookshelf with $R$ rows and $C$ columns, with one book at every position. The book at the $i$-th row from the top and the $j$-th column from the left has $P_{i,j}$ pages. Besides reading, Susu has another essential daily task: picking apples. Each day she must pick a specific apple. The apples on her family’s trees are at various heights, and she cannot reach them on her own. However, she found that if she stands on some books, she can reach the apples. She also noticed that for the apple designated on day $i$, as long as the total number of pages of the books under her feet is at least $H_i$, she will definitely be able to pick it. Because there are too many books, her parents worry she might finish reading all of them in one day and be late for kindergarten, so each day they only allow her to take books from a specific region. This region is a rectangle: on day $i$, the top-left corner is the book at row $x1_i$ and column $y1_i$, and the bottom-right corner is the book at row $x2_i$ and column $y2_i$. In other words, on that day, she can only select some books from these $(x2_i - x1_i + 1) \times (y2_i - y1_i + 1)$ books to stand on and pick the apple. Each time Susu takes books, she returns them promptly to their original places, and the bookshelf will not have books removed or added. The apple-picking task continues for $M$ days. Given the number of pages of each book, the daily region restrictions, and the picking requirement, please tell Susu the minimum number of books she must take each day to pick the specified apple.

The first line contains three positive integers $R, C, M$. Next is a matrix with $R$ rows and $C$ columns. From top to bottom and left to right, it gives the number of pages $P_{i,j}$ of each book. Then follow $M$ lines. The $i$-th line contains five positive integers $x1_i, y1_i, x2_i, y2_i, H_i$, meaning that on day $i$ the designated region is the rectangle between $(x1_i, y1_i)$ and $(x2_i, y2_i)$, and the required total number of pages is at least $H_i$. It is guaranteed that $1 \le x1_i \le x2_i \le R$ and $1 \le y1_i \le y2_i \le C$.

Output $M$ lines. On the $i$-th line, print the minimum number of books Susu needs on day $i$ to pick the apple. If she cannot pick the apple even by taking all books in the region, print `Poor QLW`.

For $10\%$ of the testdata, $R, C \le 10$. For $20\%$ of the testdata, $R, C \le 40$. For $50\%$ of the testdata, $R, C \le 200$, $M \le 2 \times 10^5$. Additionally, for $50\%$ of the testdata, $R = 1$, $C \le 5 \times 10^5$, $M \le 2 \times 10^4$. For $100\%$ of the testdata, $1 \le P_{i,j} \le 1000$, $1 \le H_i \le 2 \times 10^9$. Translated by ChatGPT 5