AcWing 2455. 合法三元组的个数
原题链接
中等
作者:
也许
,
2021-03-18 21:33:25
,
所有人可见
,
阅读 644
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 300010;
PII a[N];
int cnt[3][N];
int n;
int main()
{
int la, lb, lc, d;
cin >> la >> lb >> lc >> d;
for (int i = 1; i <= la; i++)
{
int x;
scanf("%d", &x);
a[++n] = {x, 0};
}
for (int i = 1; i <= lb; i++)
{
int x;
scanf("%d", &x);
a[++n] = {x, 1};
}
for (int i = 1; i <= lc; i++)
{
int x;
scanf("%d", &x);
a[++n] = {x, 2};
}
sort(a + 1, a + n + 1);
for (int i = 0; i < 3; i++)
for (int j = 1; j <= n; j++)
cnt[i][j] = cnt[i][j - 1] + (a[j].y == i);
int last = -1;
LL res = 0;
for (int i = 1, j = 1; i <= n; i++)
{
while (j <= n && a[j].x - a[i].x <= d) j++; //a[j].x - a[i].x > d;
if (j > last)
{
LL ta = cnt[0][j - 1] - cnt[0][i - 1]; //i ~ j - 1中属于数组A的数有几个
LL tb = cnt[1][j - 1] - cnt[1][i - 1];
LL tc = cnt[2][j - 1] - cnt[2][i - 1];
res += ta * tb * tc;
}
if (i <= last && last < j)
{
LL ta = cnt[0][last - 1] - cnt[0][i - 1];
LL tb = cnt[1][last - 1] - cnt[1][i - 1];
LL tc = cnt[2][last - 1] - cnt[2][i - 1];
res -= ta * tb * tc;
}
last = j;
}
printf("%lld\n", res);
return 0;
}