0 like 0 dislike
2,404 views
| 2,404 views

0 like 0 dislike

Image of Question :

by Expert (113,040 points)
0 like 0 dislike

Solution :

```//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 ;
}```
by Expert (113,040 points)
edited