AcWing 1236. 递增三元组
原题链接
中等
作者:
也许
,
2021-03-15 20:21:45
,
所有人可见
,
阅读 287
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N], b[N], c[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", a + i);
for (int i = 0; i < n; i++) scanf("%d", b + i);
for (int i = 0; i < n; i++) scanf("%d", c + i);
sort(a, a + n); sort(c, c + n);
LL res = 0;
for (int i = 0; i < n; i++)
{
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] < b[i]) l = mid;
else r = mid - 1;
}
int num1 = r + 1;
if (a[r] >= b[i]) num1 = 0;
l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
if (c[mid] > b[i]) r = mid;
else l = mid + 1;
}
int num2 = n - r;
if (c[r] <= b[i]) num2 = 0;
res += 1ll * num1 * num2;
}
cout << res << endl;
}