ブルーブリッジカップ増分三元グループ(列挙、二分、思考)
8678 ワード
私はテーマです.早くしてください.
考え方
列挙配列b、ばかな私は列挙配列aを始めて、それから二分は探して明細を詳しく見て注釈を参照します
コード:
考え方
列挙配列b、ばかな私は列挙配列aを始めて、それから二分は探して明細を詳しく見て注釈を参照します
コード:
#include
using namespace std;
typedef long long LL;
const int N = 1e5+9;
int a[N],b[N],c[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
sort(c+1,c+n+1);
LL ans = 0;
// b
for(int i=1;i<=n;i++)
{
// a b[i]
LL idx = lower_bound(a+1,a+n+1,b[i]) - a;
//lower_bound b[i]
// -- b[i]
idx--;
if(idx<=0) continue;
// c b[i]
LL idx2 = upper_bound(c+1,c+n+1,b[i])-c;
if(idx2==n+1) continue;
//cout<
ans+=idx*(n-idx2+1);
}
cout<<ans<<endl;
return 0;
}