arc084_a

少し紙に書いて考えたら、なるほどーって閃いた問題

中部を基準として決め打ちすると

・基準より小さいものを上部から選ぶ

・基準より大きいものを下部から選ぶ

というそれぞれの二分探索を行えば作れる祭壇のパターン数が分かる

あとは全中段のパターン数を足せばOK

#include<bits/stdc++.h>

using namespace std;

int n;

int a[100009], b[100009], c[100009];

int solve1(int p){

int ok = -1;

int ng = n;

while(abs(ok-ng)>1){

int mid = (ok+ng)/2;

if(a[mid] < p) ok = mid;

else ng = mid;

}

return ok;

}

int solve2(int p){

int ng = -1;

int ok = n;

while(abs(ok-ng)>1){

int mid = (ok+ng)/2;

if(p < c[mid]) ok = mid;

else ng = mid;

}

return ok;

}

int main(){

cin >> n;

for(int i=0;i<n;i++) cin >> a[i];

for(int i=0;i<n;i++) cin >> b[i];

for(int i=0;i<n;i++) cin >> c[i];

sort(a, a+n);

sort(b, b+n);

sort(c, c+n);

long long int cnt = 0;

for(int i=0;i<n;i++){

long long int j = solve1(b[i]);

long long int k = solve2(b[i]);

cnt += (j+1) * (n-k);

//cout << i << " " << j << " " << k << endl;

}

cout << cnt << endl;

}