Hi everyone,

I need help in a question. It came to one of the contest I gave around 4 days ago. It was a hiring contest of a good indian company.

My approach was to store ai and bi as pairs in vector and sort them. So for each query we can get the count of chocolates having sweetness greater than x using binary search on vector but now how to get the count of lifetime greater than y? I got stuck here. I still couldn't think of something. Can you tell me how to approach?

It'll be really great if anyone can help me or give me some insight.

Auto comment: topic has been updated by aim_cm (previous revision, new revision, compare).Auto comment: topic has been updated by aim_cm (previous revision, new revision, compare).Build a merge sort tree and answer queries with two binary searches. Time complexity will be $$$\mathcal{O}(Q\log^2(N))$$$.

Thank you so much. I didn't know about this. Will learn it right away. :D

Here's a good tutorial: https://discuss.codechef.com/t/merge-sort-tree-tutorial/14277

Oh thank you so much, That's so nice of you.

You do realize you could've just posted the link or taken a screenshot, right?

I am really sorry to post the screenshots like this but it was hiring contest so link was private and taking screenshot was also not allowed I guess.

Will make sure to take screenshot or take clear pictures in future.

So you are cheating?

Edit: Sorry for suspecting you for no reason. But it is weird that it is not legal for you to take the problem screenshot no more.

It was 4 days ago and it was 1.5 hrs contest. I tried to solve it on my own even after contest but couldn't. So I just posted the question and asked for help. I dont think that's cheating as I can't do or access the question now. I think it's upsolving.

It would have been better if you had mentioned all of this.

You can also solve this problem by using an offline algorithm, sort the queries and the array based on non-increasing

X. After this, the most easy way would be to use PBDS, and keep inserting valuesB[i]until yourA[i] >= X, then just count number of elements in the PBDS which are>= Y. If you don't want to use PBDS, you can use coordinate compression onB[i]and useBIT, to calculate the same, just that you would need to binary search for index while querying on theBIT. Time complexity will be —O(QlogQ + (N + Q)logN)Thanks abhishek for both these approaches. I understood the first one but can you briefly elaborate on BIT approach by taking some testcase?

The purpose of

BIThere is to count the no. of elements > Y, i.e curr_elements in BIT-elements <= Y in the BIT. So similar to inserting element in PBDS, you will doupd(B[i], 1)in the BIT, i.e increment value at indexiin theBITby 1. If the values ofB[i]lied in [1, N], we could have proceeded directly, but now, we need to compress those values into [1, N], so that we could perform our update and queries on theBIT.The only thing which you need to take care while updating and querying is that you need to find the appropriate index, and to do that, you can create a separate array

C, containing sorted order ofB[i], and use binary search to figure out the correct index to query in theBIT. For update you would have already done compression and have the index at hand. You can try this to do this on a sampleB, likeB= [10,2,-100,15,4].ㅤ

0xF5 You have to attach the querries pair with index. So after processing queries offline, you can sort queries using index and print them.

ㅤ

Sure

Ya understood it. It's somewhat similar to using BIT for inversion count problem. Thanks

ㅤ

I think the time complexity you gave is not right. Let's assume when we query we get i = 0 everytime, hence we sort (t2.begin()+0,t2.end()) which will make it nlogn. So it the complexity will become O(nlogn + Qnlogn) which will not run under 1 or 2 seconds. Let me know if I understood it wrong.

ㅤ