AM_I_Learning's blog

Doubt on this general query based question.
By AM_I_Learning, history, 4 years ago, In English

We have to handle Q queries on the array and in each query we are asked to find number of pairs {a,b} present at the moment in the array whose value are such that a<=x and b<=y for {x,y} given in the query.

Problem Link :-Codechef Bulbs

Please share the approach as I am not getting any tutorial for this problem

Please help . Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I never got why the hell you all keep calling questions "doubt". I doubt you even know the meaning of that word.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    My English is very poor sorry!!!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's not really "your" English, I have seen tons of posts using the "doubt" word like this too. Just can't stand it anymore right now.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        leave about the doubt etc.... can you explain how to solve the question in the link provided to me. I just wanted to know the approach as I am stuck from past 10 days.

        → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Sort the array initially. The array will be sorted by {a}. Then build a merge sort tree over this array using {b} values. You can perform any query in $$${O(logn)}$$$ by performing a binary-search to find a $$${l}$$$ in the array such that $$${arr[l+1].a > x}$$$ and $$${arr[l].a<=x}$$$. Then query for count of values <= $$${y}$$$ in range $$$[1,l]$$$ using merge sort tree.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Divide and Conquer passes but barely: https://www.codechef.com/viewsolution/30575723

→ Reply