Given an array of size n with n<10^5
Given q queries where q<50000
A query q is of the form
Q a
where a is an integer, you have to subtract one from values at index i,if array[i]>a
Print the final array
What problem are you facing?
Please add a link of question…
use brute force technique : for each query check
if (array[i] > a)
{array[i] = array[i] - a}
print the final array… 
but you could have also done it . But if the query is asking for interval or after some query want you to print the interval then this problem is of (segment tree)
Brute Force gives out tle (5*10^9 operations at the max)
Newbie to Segment/Fenwick trees
Couldn’t think of an optimal approach via segment tree
no brute force will have complexity of O(query) cause each query have complexity of O(1) don’t know how you manipulated it as 5*10^9 .
suppose the array is {1,2,3,4,5,6,7,8,9}
and there are 100 queries then each query will have only one operation :if (array[i] > a) {array[i] -= a}
still may be you should provide the link to the problem then cause looking at the problem right now all i can think of this .
We are not given a specific index i
Instead we have to traverse the whole array and reduce all the values by 1 which exceed a for every query
Hence for 50000 queries we will have (50000*100000) worst case time
You can use a segment tree. First u can sort the array! Now after every query the array will still be sorted. Now to reduce the array elements you will have a range to reduce by 1. Which is basically range update for which u can easily find a code online. It will involve lazy propagation. After the queries u can print the original array. For that u will need to save the position of the numbers initially using a map or something!
Hope this helps
Hello all,
This problem is from ongoing contest of Dhruva hiring contest HackerEarth. @nidhi1234 please solve problems in fair manner.
Contest link : Druva Development Engineers' Challenge
sorry for getting the question wrong and here as you mentioned that we have to reduce 1 from those elements whoever have the value greater than (a) . What you have to do is first generate a map-pair for array and then you have to sort the array and then use segment array for that the update query will work . Update the value of the array to +1 , for then keep track the left and the right index of the segment now after all those queries you can come back to the original array using the map-pair that we created initially … (Happy coding)
this link might be helpful for segment tree + segment tree with lazy propagation …
As you can see the time which users took to respond to the question was more than time allotted for the test , I was not here to cheat in some way.
I wanted to know the concept behind such query question
But I’ll make sure that I ask the question,if it features in any contest, only after the contest ends