Question

Microsoft | OA Coding Questions and Solutions | Set - 26 | 2022

Answer 1

Image of Question : 

Answer 2

//TC O(NLOGN)

#include <bits/stdc++.h>
using namespace std ;
typedef long long int ll ;

int main() {
  

    ll n;
    cin>>n;

    ll i = 0 ;
    vector <ll> k,start ;
    vector <pair<ll,ll>> s ;

    while(i<=n-1){
        ll x;
        cin>>x;
        start.push_back(x);
        i++;
    }

    i = 0 ;
     while(i<=n-1){
        ll y;
        cin>>y;
        k.push_back(y);
        i++;
    }

    i = 0 ;
    while(i<=n-1){
        s.push_back({start[i],k[i]});
        i++;
    }

    start.push_back(-1e18);
    start.push_back(1e18);

    k.push_back(-1e18);
    k.push_back(1e18);

    sort(start.begin(),start.end());
    sort(k.begin(),k.end());

    ll ans = 0 ;
    i = 0 ;
    while(i<=n-1){
        ll x = s[i].first ;
        ll y = s[i].second ;

        //number of elements smaller than x in vector k
        auto mg = lower_bound(k.begin(),k.end(),x);
        auto kk = mg - k.begin() ;
        ll ram = kk ;
        ll osi1 = kk - 1 ;

         //number of elements smaller than y in vector start
       

        mg = upper_bound(start.begin(),start.end(),y);
        kk = mg - start.begin() ;
        ram = kk ;
        ll osi2 = (n+1-kk) ;

        cout<<osi1<<" "<<osi2 ;
        cout<<"\n";
        ans = ans + osi1*osi2 ;
      

        i++;
    }
    cout<<ans ;
  
  
  
  
  

    return 0 ;
}