Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution F - Counter RMQ

F. Counter RMQ
Score: 1

 CPU: 1s
Memory: 1200MB
You must have heard about the Range Minimum Query (RMQ) problem. If you haven’t, here is a definition:
Given an array A[1 … n] of n integers, the range minimum query RMQ(l, r) (1 ≤ l ≤ k ≤ r ≤ n) returns the value of the minimal element in the specified sub-array A[l … r].
Imagine a program that takes a series of RMQ queries and prints the answers. Is it possible to recover the original sequence? Yes, you are right, it’s not possible for most of the cases, for different possible input arrays A, there could be the same set of answers for a given set of RMQ queries. Why don’t we try finding one such array A?
Given n, (the length of A) and q RMQ queries and their answers in l r RMQ(l, r) format, print any array that produces the answer. For the purpose of this problem, we assume A[i] will be positive and less than or equal to 20000.

Input

The input starts with T, the number of test cases (T ≤ 100). It follows T sets of test cases. Each test case starts with two numbers n andq (1 ≤ n ≤ 100, 1 ≤ q ≤ 20000) denoting the array length and the number of queries. That is followed by q lines. Each of these q lines consists of three integers l, r, RMQ(l, r) as mentioned in the statement. (1 ≤ l ≤ r ≤ n and 1 ≤ RMQ(l, r) ≤ 20000). You can assume that there will always be at least one valid answer consistent with the input.

Output

For each set of inputs, print the test case number followed by the output array, n integers separated by single space. For the output format, please consult the sample input/output. There can be multiple correct answers, you can print anyone.

Sample

InputOutput
1 7 5 1 4 4 4 7 12 2 2 17 1 7 4 4 5 32 Case 1: 10 17 4 57 32 53 12
*Warning: Large I/O file, user faster input output functions.











Comments

Post a Comment

Popular posts from this blog

Solution - Timus Problem 1293. Eniya

1293. Eniya Time limit: 1.0 second Memory limit: 64 MB It’s restless now on the slips of the intergalactic port’s sixth dock of planet of Torn. No longer then in a month the reconstruction of the small ironclad corvette “Eniya” will be finished. And again this battle ship and its brave team would have to struggle for the control over plutonium mines of Sibelius. The work cannot be stopped even for a second, self-powered laser welders work round the clock. Joints of robots-repairers fuse because of this permanent work. Nevertheless, they can’t stop not for a single moment. Now in all this turmoil it is discovered that corvette’s thermopanels again need an urgent processing with thorium sulphide. It is known that the processing of the one square meter of the panel needs 1 nanogramm of sulphide. In general, it is needed to process  N  rectangular panels, which dimensions are  A  by  B  meters. It is necessary to calculate as fast as possible, how m...
Read more...

Solution - Codeforces Problem 327B - Hungry Sequence

B. Hungry Sequence Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of  n  integers. A sequence  a 1 ,  a 2 , ...,  a n , consisting of  n  integers, is  Hungry  if and only if: Its elements are in increasing order. That is an inequality  a i  <  a j  holds for any two indices  i ,  j   ( i  <  j ) . For any two indices  i  and  j   ( i  <  j ) ,  a j  must  not  be divisible by  a i . Iahub is in trouble, so he asks you for help. Find a Hungry sequence with  n  elements. Input The input contains a single integer:  n  ( 1 ≤  n  ≤ 10 5 ). Output Output a line that contains  n  space-separated integers  a 1   a 2 , ...,  a n   (1 ≤  a i  ≤ 10 7 ) , representing a ...
Read more...

Solution - Timus Problem 1409. Two Gangsters

1409. Two Gangsters Time limit: 1.0 second Memory limit: 64 MB Two gangsters Harry and Larry had a rest at countryside. They decided to spend some time shooting, so they put several beer cans (no more than 10) on a log. Harry started to shoot cans one after another from the leftmost to the right and Larry – from the rightmost to the left. At some moment it happened so that they shot one and the same can. Harry got indignant and claimed that Larry owed him a considerable sum of money because Larry deprived him of shooting some more cans. Larry became furious and told Harry that he owed even greater sum of money to Larry because of the same reason. They started to argufy but nobody remembered how many cans there were at the very beginning. And no one of them was going to search cans which was shot. Anyway, each of them remembered exactly how many cans he shot. Determine how many cans were not shot by Harry and how many cans were not shot by Larry. Input The only inp...
Read more...