AcWing 1236. 递增三元组
原题链接
中等
作者:
虚实相依
,
2024-04-13 00:05:24
,
所有人可见
,
阅读 1
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1e5+10;
typedef long long ll;
int n;
int a[N];
int b[N];
int c[N];
ll ans;
ll check_a(int tmp)
{
int l=1,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid]>=tmp) r=mid-1;
else l=mid;
}
if(a[l]>=tmp) return 0;
return l;
}
ll check_c(int tmp)
{
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
if(c[mid]<=tmp) l=mid+1;
else r=mid;
}
if(c[l]<=tmp) return 0;
return n-l+1;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) cin>>c[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n);
sort(c+1,c+1+n);
for(int i=1;i<=n;i++)
{
int tmp=b[i];
ll x=check_a(tmp);
ll y=check_c(tmp);
ans+=x*y;
}
cout<<ans<<endl;
return 0;
}