Mock CCC '23 Contest 1 J5 - Calculus Problem

View as PDF

Submit solution

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

Author:
Problem type

Tommy and Alan decide to celebrate \mathrm e-day by doing some calculus problems with their Q friends!

There are N problems, and the i-th problem gives d_i points. The j-th person has a difficulty adjustment of m_j, which means that the i-th problem has an adjusted difficulty of m_j \oplus i. Additionally, the j-th person can only solve problems which have an adjusted difficulty of at most k_j. That is, the j-th person can solve the i-th problem if m_j \oplus i \le k_j.

For each of the Q people, can you figure out, over all the problems they can solve, which will give them the most points?

\oplus stands for the bitwise XOR operator (e.g. 0110 \oplus 1010 = 1100).

Input Specification

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

The second line contains N space-separated integers d_0, d_1, \dots, d_{N-1} (1 \le d_i \le 10^6).

The next Q lines each contain the description of one of Tommy and Alan's friends. Each query contains two space-separated integers m_j (0 \le m_j < N) and k_j.

The following table shows how the available 15 marks are distributed.

Mark AwardedNumber of ProblemsNumber of QueriesAdditional Constraints
3 marks1 \le N \le 10^31 \le Q \le 10^31 \le k_j \le 10^3
3 marks1 \le N \le 10^51 \le Q \le 10^51 \le k_j \le 10^6
9 marks1 \le N \le 10^61 \le Q \le 5 \times 10^51 \le k_j \le 10^6

Output Specification

For each person, output the number of points of the hardest problem they can solve. It can be proven that at least one problem is always possible.

Sample Input 1

5 2
1 2 3 4 5
1 3
2 4

Output for Sample Input 1

4
4

Explanation of Output for Sample Input 1

Person 1 can do problems 0, 1, 2, and 3. Of those, problem 3 gives the most points, 4.

Person 2 can also gain 4 points by doing problem 3.

Sample Input 2

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

Output for Sample Input 2

9
4

Explanation of Output for Sample Input 2

Person 1 can do problems 0, 1, 2, 3, and 6. Problem 0 gives 9 points, which is the highest.

Person 2 can score 4 points by doing problem 6.


Comments

There are no comments at the moment.