K stacks and Plates

All submissions for this problem are available.
Chingam likes to collect plates because they remind him of food. But Jimma hates plates, because they make a lot of noise when they break. Chingam has a collection of N plates hidden behind Jimma's bed, so that she cannot find them. The plates are arranged in K stacks, such that each stack has at least one plate. The stacks are indexed from 0 to K1. Where 0 is index of the leftmost stack and K1 is the index of the rightmost stack.
Every plate has a weight w and a capacity c. These values might be different for different plates. A plate breaks when the sum of weights of the plates kept above it exceeds its capacity.
Whenever Chingam finds a new plate, he adds it to one of the K stacks. The plate is always added to the top. After he does this, some of the plates in that stack break. As Jimma is always sleeping and plotting world domination, if too many plates break at the same time, she will wake up and scratch Chingam. So Chingam will always choose the stack which minimize the number of plates that break and hope that the noise is not too loud. If there are multiple ways to do that, then he will place the plate in the leftmost such stack. Chingam is not very good at counting and he cannot always find the best stack on his own. Please help him!
You are given the initial arrangement of N plates in the stacks and Q queries. Query i describes a plate with capacity C[i] and weight W[i]. You have to tell Chingam the index of the best stack for this plate and the number of plates which break after this plate is added to that stack.
Chingam will then add the plate to that stack.
Note:
The plates should be added in the order they appear in the queries.
A plate can break only once and its weight does not change after it breaks.
It is guaranteed that there are no broken plates in the initial arrangement; i.e. for every plate, the sum of plates on top of it will not exceed its capacity.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains the integer K and is followed by K lines.
 The i^{th} such line describes the i^{th} stack. The first integer on that line is n[i] the number of plates in that stack and is followed by 2*n[i] space separated integers. The 2*j^{th} and 2*j+1^{th} integers on that line give the capacity and the weight repectively, of the j^{th} plate from the bottom.
 The next line contains an integer Q, the number of queries and is followed by Q lines
 Each of these lines contain two space separated integers, the capacity and the weight of the plate in that query.
Output
 For each test case, output Q lines, one for each query. Each line should contain two integers  the first integer should be the index of the best plate for that query and the second integer should be the number of plates which break in that query.
Constraints
 1 ≤ T ≤ 3
 1 ≤ K ≤ 5*10^{4}
 1 ≤ Q ≤ 10^{5}
 The total number of plates (Q+N) in each test case will not exceed 10^{5}.
 All the weights and capacities are positive integers and do not exceed 10^{9}
Example
Input: 1 3 2 5 10 3 3 2 7 15 2 1 1 2 8 2 3 4 9 5 Output: 1 1 2 1
Explanation
Example case 1. There are 3 stacks and 2 queries. The first query has a plate of capacity 3 and weight 4. Placing that plate in the stack numbered 0 will break both the plates in that stack. Placing it in one of the other two stacks breaks only one plate. Chingam should place it in the leftmost stack, hence the output is 1 1.
Now stack 1 has three plates and one of them is broken. Placing the next plate in either stack 0 or 1 will break two plates, while placing it in stack 2 will break only one. Hence the output is 2 1
.
Author:  meteora 
Tags  meteora 
Date Added:  29012016 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions