the link to the problem is this.

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

I am getting tle on one case .

Can anyone suggest some approach to this problem .

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

## AC_CODE

```
#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

6 Likes

Thanks a lot !!

2 Likes