Help Needed with Nested Range Count , CSES

1

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 .

2

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

7 Likes
3

Your AC_CODE just change map to unordered map

2 Likes
4

Thanks a lot !!

2 Likes
5

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

4 Likes
6

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/