| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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.
I never got why the hell you all keep calling questions "doubt". I doubt you even know the meaning of that word.
My English is very poor sorry!!!
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.
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.
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.
Divide and Conquer passes but barely: https://www.codechef.com/viewsolution/30575723
Can you write the algorithm or the pseudocode it will be really helpful!!!
Check out this link and this. The first problem on the second link is exactly this problem.
thank you so much