Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #include <deque>
- #include <algorithm>
- #include <bitset>
- #include <cmath>
- #include <string>
- #include <set>
- #include <iomanip>
- #include <queue>
- #include <bitset>
- #include <unordered_map>
- using namespace std;
- #define pb push_back
- #define ll long long
- #define mp make_pair
- #define X first
- #define Y second
- #define ld long double
- const int N = 2e6;
- int dpsum[N][3];
- ll dp1[N][3][3];
- int dp2[N][3];
- void relax(int i)
- {
- for(int j = 0; j <= 2; j++)
- {
- if(i > 0)
- {
- dpsum[i][j] = dpsum[i - 1][j];
- dp2[i][j] = dp2[i - 1][j];
- }
- for(int k = 0; k <= 2; k++) dp1[i][j][k] = dp1[i - 1][j][k];
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int d;
- while(cin >> d)
- {
- int n1 , n2 , n3;
- cin >> n1 >> n2 >> n3;
- int sz = n1 + n2 + n3;
- long long ans = 0;
- vector<pair<ll , int> > a(sz + 1);
- for(int i = 1; i <= n1; i++)
- {
- cin >> a[i].first;
- a[i].second = 0;
- }
- for(int i = 1; i <= n2; i++)
- {
- cin >> a[i + n1].first;
- a[i + n1].second = 1;
- }
- for(int i = 1; i <= n3; i++)
- {
- cin >> a[i + n1 + n2].first;
- a[i + n1 + n2].second = 2;
- }
- sort(a.begin() + 1, a.end());
- for(int i = 1; i <= sz; i++)
- {
- relax(i);
- ll j = a[i].second;
- dpsum[i][j]++;
- dp2[i][j] = i;
- for(int k = 0; k <= 2; k++) dp1[i][j][k] += dpsum[i][k];
- }
- for(int i = 1; i <= sz; i++)
- {
- for(int j = 0; j <= 2; j++)
- {
- if(a[i].second != j)
- {
- int k = 3 ^ a[i].second ^j;
- int ind = lower_bound(a.begin() + 1, a.end(), mp(a[i].first + d + 1 , -1)) - a.begin() - 1;
- // cout << closest << " " << ind << "\n";
- if( dp2[ind][j] < i) continue;
- // cout << "zjhskejzhfkja";
- ans += 1LL * (dp1[dp2[ind][j]][j][k] - dp1[i][j][k]);
- ans -= 1LL * (dpsum[dp2[ind][j]][j] - dpsum[i][j]) * dpsum[i][k];
- }
- }
- }
- cout << ans << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement