Baking Pizza
Time limit2sMemory limit256 MB
Simulate inserting pizza doughs into a tapering tube oven, each settling as deep as possible above prior doughs, and report the final dough's position or 0 if any fails to fit.
- Level
Medium5 of 10
- Topics
- Binary search, Prefix sum, Greedy, Simulation
- Solved
- No attempts yet
Problem
At World Pizza's Wonju branch, N pizza doughs are baked by placing them into a tube-shaped oven of depth D. The oven's diameter may differ at each depth, and each dough may also have a different diameter.
The doughs are inserted one by one in the order they are completed. A dough cannot pass through any part of the oven whose diameter is smaller than the dough's diameter, and it is placed at the deepest available position it can reach, above any doughs already placed. After all N doughs have been inserted, determine the position of the topmost dough, which is the last inserted dough. If not all doughs can fit in the oven, output 0.
Input
The first line contains two integers D and N, the depth of the oven and the number of pizza doughs. (1 <= D, N <= 300,000)
The second line contains D integers: the oven diameters from the top of the oven to the bottom.
The third line contains N integers: the diameters of the doughs in the order they are completed.
Every oven diameter and dough diameter is a positive integer at most 1,000,000,000.
Output
Print the position of the last pizza dough on the first line. The top of the oven is position 1, and the deepest bottom position is D. If not all doughs can be inserted into the oven, print 0.
Hint
No additional hint is provided.