Query Problem

Revision en1, by CP_Sucks, 2019-09-14 12:56:42

I was doing a problem on Hackerearth contest, it was similiar to a problem i solved in one of the codeforces round but was more difficult than that.

Problem : We start from nothing. There are 4 type of queries -> 1. A x -> adds element x in array 2. I x -> increases value of all elements in array A by x 3. D x -> decreases value of all elements in array A by y 4. P k -> print the kth greatest element in the array so far

I don't remember the constraints but they were large enough that brute force won't work.

I know these types of problems can be solved by using suffix array for updating values and i tried that but couldnt figure out how to handle the query of type 4.

Any help would be appreciated

Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English CP_Sucks 2019-09-14 12:56:42 761 Initial revision (published)