How to approach and what data structure to use for such problem?

I recently encountered a problem in one of the hiring contest of hackerearth not to worry the contest has been ended and here goes the link to the contest as a proof https://www.hackerearth.com/challenges/hiring/cambium-networks-hiring-2019/ :slightly_smiling_face:
just wanted to know about this problem like what data structure can one use to find the answer to this problem and how to generally approach these kind of questions.

You need a list of your pokemons sorted by power (X).
Note that the order of the list never changes.
But, on A operation one entry is inserted.
On P operation you need to access element at position K.

So you need a structure to allow both, quick insert and random access.
Since Q is limited to 20000 the list is rather small, so using vector could provide fast enough insert method.
If that is to slow you probably need to use some tree like structure, for expample

same solution but just change I and D operation.
for I and D instead of updating whole BIT tree just update a delta variable as delta=delta+X or delta=delta -X
and while inserting insert delta+x
and while printing ans print (ans-delta)

1 Like

@yaman_47 and @spookywooky thanks for you support and @yaman_47 windows activation is never gonna happen it is a sign of being a true indian. :rofl::rofl:

1 Like