# Help Needed with Nested Range Count , CSES

**URL:** <https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014>\
**Category:** Uncategorized\
**Created:** [January 16, 2021, 9:08am UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014 "2021-01-16T09:08:29Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![bhavyashah12](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@bhavyashah12](https://discuss.codechef.com/u/bhavyashah12)\
**Post date:** [January 16, 2021, 9:08am UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014/1 "2021-01-16T09:08:29Z")

</div>

the link to the problem is [this](https://cses.fi/problemset/task/2169).  
I have tried using fenwick tree .  
my logic was as follows :  
1 ) used coordinate compression on the ranges  
2 ) made a vector of the type {{left,type = 0},{right,index}} , {{right,type = 1},{left,index}}  
3 ) type == 0 means starting a range  
4 ) type == 1 means range is over  
5) sort the vector  
6 ) while traversing the vector :  
a) if type is 0 , we are starting the range , to know how many ranges contain  
this range we need to know how many right index are present such that their  
range is started and are \>= then the right index of this range. I have used fenwick  
tree for this purpose .After i get the answer i update the fenwick tree1 by increasing  
the count of the right index .  
b ) if type is 1 , we know the range is finished , to know how many ranges are within  
this range , we need to check how many left index are present such that its range  
is finished and it is \>= left index of this range. I have used fenwick tree2 for this  
purpose . After getting the answer we update the fenwick tree2 by increasing the  
count of the left index .  
the link to my solution is [here](https://cses.fi/paste/0a4d6668b2ec679a178acb/)  
I am getting tle on one case .  
Can anyone suggest some approach to this problem .

---

<div class="post-metadata">

**Author:** ![cubefreak777](https://discuss.codechef.com/user_avatar/discuss.codechef.com/cubefreak777/32/215911_2.png) [@cubefreak777](https://discuss.codechef.com/u/cubefreak777)\
**Post date:** [January 16, 2021, 12:17pm UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014/2 "2021-01-16T12:17:40Z")

</div>

My Solution using policy based data structures, your approach is correct I also implemented the same idea using pbds.

> **AC\_CODE**
>
> ```auto
> #include<bits/stdc++.h>
> #include <ext/pb_ds/assoc_container.hpp>
> #include <ext/pb_ds/tree_policy.hpp>
> using namespace __gnu_pbds;
> using namespace std ;
> #define ar array
> template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
> signed main(){
> int n ; cin >> n ;
> oset<ar<int,2>>b,c;
> vector<ar<int,3>>a(n) ;
> vector<int>A(n),B(n) ;
> for(int i=0;i<n;i++)
> cin >> a[i][0] >> a[i][1],a[i][2]=i ;
>     
> sort(a.begin(),a.end(),[&](const ar<int,3> i,const ar<int,3>j){
> return ((i[0]<j[0])||(i[0]==j[0]&&i[1]>j[1])) ;
> }) ;
> for(int i=0,j=n-1;i<n;i++,j--){
> A[a[i][2]]=i-b.order_of_key({a[i][1],-1}) ;
> B[a[j][2]]=c.order_of_key({a[j][1]+1,-1}) ;
> b.insert({a[i][1],i}) ;c.insert({a[j][1],i}) ;
> }
> for(int i=0;i<n;i++)
> cout << B[i] <<' ' ;
> cout << '\n' ;
> for(int i=0;i<n;i++)
> cout << A[i]<< ' ' ;
> }
> 
> ```

PS: The links you gave in the post are swapped

---

<div class="post-metadata">

**Author:** ![cubefreak777](https://discuss.codechef.com/user_avatar/discuss.codechef.com/cubefreak777/32/215911_2.png) [@cubefreak777](https://discuss.codechef.com/u/cubefreak777)\
**Post date:** [January 16, 2021, 12:45pm UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014/3 "2021-01-16T12:45:56Z")

</div>

Your [AC\_CODE](https://cses.fi/paste/1c3797c9396f42ab178fd0/) just change map to unordered map

---

<div class="post-metadata">

**Author:** ![bhavyashah12](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@bhavyashah12](https://discuss.codechef.com/u/bhavyashah12)\
**Post date:** [January 16, 2021, 3:17pm UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014/4 "2021-01-16T15:17:30Z")

</div>

Thanks a lot !!

---

<div class="post-metadata">

**Author:** ![priyansh19077](https://discuss.codechef.com/user_avatar/discuss.codechef.com/priyansh19077/32/355172_2.png) [@priyansh19077](https://discuss.codechef.com/u/priyansh19077)\
**Post date:** [January 17, 2021, 5:54am UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014/5 "2021-01-17T05:54:51Z")

</div>

You can check this out for a clear video explanation if that helps:

[![](https://img.youtube.com/vi/Lyi7N_cB55w/maxresdefault.jpg "CSES Problem Set: Nested Ranges Count(Hard Version) | Fenwick Trees, Two Pointers, Sorting | English") ](https://www.youtube.com/watch?v=Lyi7N_cB55w)

---

<div class="post-metadata">

**Author:** ![crochold](https://discuss.codechef.com/user_avatar/discuss.codechef.com/crochold/32/24644_2.png) [@crochold](https://discuss.codechef.com/u/crochold)\
**Post date:** [October 10, 2021, 12:29pm UTC](https://discuss.codechef.com/t/help-needed-with-nested-range-count-cses/84014/6 "2021-10-10T12:29:01Z")

</div>

bro… did the same thing…im getting tle on 5th and 9th test…  
earlier i was getting tle on several cases but then i used -ios… cin.tie(0)cout.tie(0) stuff, and i got ac.  
the 5th and 9th testcases are giving tle by 0.08/9 secs i believe, (i know coz i tried running diffn sections of code, seperately, to check the time for testcases).  
are there any other tweaks i can make to make the code faster?  
my code-[https://cses.fi/paste/a435335370beae5f2d6633/](https://cses.fi/paste/a435335370beae5f2d6633/)