COCI '22 Contest 5 #4 Slastičarnica

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

There is a new bakery in town! Come and try delicious cakes from Dodo's bakery!

The bakers have prepared n cakes, the i-th of which has sweetness a_i. They are displayed on a long table in the given order. There are q people waiting in line to order the best cakes in town. Each of them has an order of the form: "I would like to buy d_i cakes whose sweetnesses are at least s_i".

Dorijan serves customers in a peculiar way. He will give d_i continuous cakes from the table. To keep the table looking as nice as possible, he will only give cakes from the left or the right end of the table. He noticed that he cannot serve a lot of customers that way, so before serving a customer, he will eat some cakes (possibly none) from the ends of the table.

If Dorijan cannot satisfy a customer, he will close the bakery for the day. What is the largest number of customers he can serve before closing?

Input Specification

The first line contains two integers n, q (1 \le n \le 5\,000, 1 \le q \le 2 \times 10^5), the number of cakes and the number of people in the line.

The second line contains n integers a_i (1 \le a_i \le 10^9), where a_i is the sweetness of the i-th cake.

In each of the next q lines there are two integers d_i, s_i (1 \le d_i \le n, 1 \le s_i \le 10^9), the order of the i-th customer in the line.

Output Specification

In the first and only line, output the number of customers Dorijan can serve.


Subtask Points Constraints
1 21 n, q \le 100
2 31 d_1 = d_2 = \dots = d_q = 1
3 58 No additional constraints.

Sample Input 1

5 6
1 2 3 4 5
1 1
1 2
1 3
1 4
1 6
1 5

Sample Output 1


Sample Input 2

5 3
1 3 2 2 1
3 1
1 3
2 2

Sample Output 2


Sample Input 3

9 5
1 3 2 5 1 4 6 2 1
3 2
2 3
1 1
1 2
1 1

Sample Output 3


Explanation for Sample 3

Dorijan first eats one cake from the left, then gives the next three cakes with sweetnesses 3, 2, and 5 to the first customer. He then eats another cake from the left and gives the next two cakes with sweetnesses 4 and 6 to the second customer. The third customer gets a cake from the right with sweetness 1 and the fourth gets the last cake with sweetness 2. Dorijan unfortunately does not have more cakes, so the last customer goes home empty-handed.


There are no comments at the moment.