740 . Sunset Posters
Description
Sunset Street is a very shiny street in a tiny town called Sunset Town. Everyday when the sun
sets, the whole street is soaked in the glow and houses form a beautiful skyline. These days there
will be a music festival held in Sunset Town. In order to decorate the main street, Sunset Street,
the organizer decides to put some posters up the wall on the houses.
But the things have been more complicated now. Due to the shortage of funds, the organizer
can only afford to produce one size for the posters. So the organizer’s first problem is to estimate
the best poster size. Consider the street’s skyline, as shown in the figure below.
Once the size of the poster is determined, all they have to do is to put as many posters up to
the wall. For some reason, the bottom of each poster should touch the ground of the street.
Therefore, the largest number of posters which can be put up to the wall decides the fitness of a
poster size. Please write a program that helps the organizer to count the maximum posters that
can be put on the wall when the size of a poster is determined.
Note that all the posters are rectangle-shaped, and they cannot be overlapped. Every part of
a poster should be stick up on the wall tightly.
Input Format
There will be one or more test cases in the input file.
For each test case, the first line contains two numbers n (1 ≤ n ≤ 100, 000) and q (0 ≤ q ≤
10, 000), indicating the length of the street and the number of questions respectively. The next
n non-negative integers, separated by one or more space or newline characters, are the heights of
the wall, from left to right. Then the next q lines are questions. Each line contains two positive
integers W,H (1 ≤ W ≤ n, 1 ≤ H < 231
) indicating the width and the height of the poster size.
All the numbers will not exceed 231
− 1.
n = q = 0 indicates the end of the input, as shown in the sample input. Don’t process it.
Output Format
For each question output a line contains a number k, the maximum number of the posters can be
put up onto the wall.
Print a blank line between consecutive test cases.
Sample Input 1
15 3 3 3 5 5 2 2 6 6 4 4 5 5 5 1 1 3 4 1 1 5 5 2 1 5 7 2 1 0 0
Sample Output 1
2 15 0 1
Hints
Problem Source
Migrated from old NTUJ.
PTC
Subtasks
| No. | Testdata Range | Score |
|---|