Appleby Contest '20 P2 - Playful Playdoughs

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Plasmatic loves playing with playdoughs in his spare time. Currently, he has a collection of N playdoughs, and the i^\text{th} playdough weighs a_i grams for each i from 1 to N. However, he is too busy practicing for IOI. As a result, he doesn't have much time to play with the playdoughs. Instead, he gives you Q operations that he wants you to do with his collection of playdoughs, and each operation can be one of the two:

  1. 1 x: Find all playdoughs that weighs exactly x grams then split the playdough into \lceil \frac{x}{2} \rceil and \lfloor \frac{x}{2} \rfloor.

  2. 2 y: Find the number of playdoughs that weigh exactly y grams.

As a good friend of him, you want to print the answers for all of the queries in the form of 2 y. Do not disappoint him!

Constraints

Subtask 1 [15%]

1 \le N \le 100

1 \le Q \le 500

1 \le a_i, y \le 100

2 \le x \le 100

Subtask 2 [85%]

1 \le N \le 10^5

1 \le Q \le 5 \cdot 10^5

1 \le a_i, y \le 10^5

2 \le x \le 10^5

Note that a 64-bit integer is needed to get full points. In C++, this can be done with long long. In Java, this can be done with long. In Python, the standard int will suffice.

Input Specification

The first line contains two integers N and Q separated by a space.

The next line contains N integers a_i, the weight of each of his playdough originally.

The following Q lines each contains two space-separated integers, indicating a valid query.

Output Specification

Print the answer to each query of the second type, followed by a newline.

Sample Input

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

Sample Output

4
2

Comments


  • 0
    Jinx  commented on Dec. 23, 2021, 10:45 a.m. edited

    Is it just me that finds it odd that someone has time to divide and sort 100 thousand playdoughs for their friend?

    Edit: This is a joke!