-2

Given q queries of the following form. A list is there.

1 x y: Add number x to the list y times.

2 n: find the nth number of the sorted list

constraints

1 <= q <= 5 * 100000

1 <= x, y <= 1000000000

1 <= n < length of list

sample. input

4

1 3 6

1 5 2

2 7

2 4

output

5

3

Coder doit
  • 25
  • 5
  • Welcome to Stack Overflow. Please read https://stackoverflow.com/help/how-to-ask and especially http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions. The idea here is not for us to do your homework for you, but for you to attempt it, show us some code (or describe your potential solution), and for us to help guide you to a solution. – Jim Mischel Nov 06 '18 at 22:56
  • In your sample input, what is the "3" on the first line? – Jim Mischel Nov 06 '18 at 22:57
  • I am sorry thats "4" or no of queries..... – Coder doit Nov 07 '18 at 06:34
  • I tried implementing it with map but got tle for some test cases. – Coder doit Nov 07 '18 at 06:36
  • If you read the links about how to ask a good question, you didn't follow the suggestions. You need to post your code that attempts to solve the problem so that we can help you understand where you went wrong and how to fix it. – Jim Mischel Nov 07 '18 at 12:53

1 Answers1

1

This is a competitive programming problem that it's too early in the morning for me to solve right now, but I can try and give some pointers.

If you were to store the entire array explicitly, it would obviously blow out your memory. But you can exploit the structure of the array to instead store the number of times each entry appears in the array. So if you got the query

1 3 5

then instead of storing [3, 3, 3], you'd store the pair (3, 5), indicating that the number 3 is in the list 5 times.

You can pretty easily build this, perhaps as a vector of pairs of ints that you update.

The remaining task is to implement the 2 query, where you find an element by its index. A side effect of the structure we've chosen is that you can't directly index into that vector of pairs of ints, since the indices in that list don't match up with the indices into the hypothetical array. We could just add up the size of each entry in the vector from the start until we hit the index we want, but that's O(n^2) in the number of queries we've processed so far... likely too slow. Instead, we probably want some updatable data structure for prefix sums—perhaps as described in this answer.

ameed
  • 1,132
  • 6
  • 25