Chef at the Olympics Codechef October Long Challenge

by

Chef at the Olympics Solution

The Chef is at the Olympics. You are given the medal tally of N of the participating countries. You are also given Q queries, each represented by a single integer K. For each such query, you need to find the best possible rank country 1 can achieve if you are allowed to take any K medals (possibly of different countries) and change their color.

Note:

  • Countries are ranked lexicographically in order of their gold, silver, and bronze medals. If countries i and j have the same number of gold, silver, and bronze medals, then country i is considered to be ahead of country j if and only if i<j. There are no ties in the rank list.
  • Since the input-output is large, prefer using fast input-output methods.

Input Format

  • The first line contains T denoting the number of test cases. Then the test cases follow.
  • The first line of each test case consists of two space separated integers N and Q denoting the number of countries and the number of queries.
  • N lines follow. The i-th line consists of three separated integers G, S, and B indicating that the i-th country has won G gold medals, S silver medals, and B bronze medals.
  • Q lines follow. The i-th line line consists of a single integer K describing the i-th query.

Output Format

For each query, output on a single line the best possible rank of country 1.

Constraints

  • 1≤T≤105
  • 1≤N≤105
  • 1≤Q≤105
  • 0≤B,S,G≤5⋅108
  • 0≤K≤1015
  • Sum of N over all testcases is at most 5⋅105.
  • Sum of Q over all testcases is at most 5⋅105.

Subtasks

Subtask 1 (100 points): Original constraints

Sample Input 1

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

Sample Output 1

3
1
1

Explanation

  • Test Case 1: We will change one bronze medal of country 1 to a gold medal.
  • Test Case 2: We will change two bronze medals of country 1 to gold medals.
  • Test Case 3: We will change three silver medals of country 1 to gold medals.

Sample Input 2

1
2 1
2 0 0
2 1 0
1

Sample Output 2

1

Explanation

Test Case 1: The only way is to change one of the gold medals of country 2 to a silver or bronze medal.

October Long Challenge 2021

Leave a Comment

5 × one =