Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <deque>
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <cmath>
  8. #include <string>
  9. #include <set>
  10. #include <iomanip>
  11. #include <queue>
  12. #include <bitset>
  13. #include <unordered_map>
  14. using namespace std;
  15. #define pb push_back
  16. #define ll long long
  17. #define mp make_pair
  18. #define X first
  19. #define Y second
  20. #define ld long double
  21. const int N = 2e6;
  22. int dpsum[N][3];
  23. ll dp1[N][3][3];
  24. int dp2[N][3];
  25. void relax(int i)
  26. {
  27. for(int j = 0; j <= 2; j++)
  28. {
  29. if(i > 0)
  30. {
  31. dpsum[i][j] = dpsum[i - 1][j];
  32. dp2[i][j] = dp2[i - 1][j];
  33. }
  34. for(int k = 0; k <= 2; k++) dp1[i][j][k] = dp1[i - 1][j][k];
  35. }
  36. }
  37. int main()
  38. {
  39. ios_base::sync_with_stdio(0);
  40. cin.tie(0);
  41. cout.tie(0);
  42. int d;
  43. while(cin >> d)
  44. {
  45. int n1 , n2 , n3;
  46. cin >> n1 >> n2 >> n3;
  47. int sz = n1 + n2 + n3;
  48. long long ans = 0;
  49. vector<pair<ll , int> > a(sz + 1);
  50. for(int i = 1; i <= n1; i++)
  51. {
  52. cin >> a[i].first;
  53. a[i].second = 0;
  54. }
  55. for(int i = 1; i <= n2; i++)
  56. {
  57. cin >> a[i + n1].first;
  58. a[i + n1].second = 1;
  59. }
  60. for(int i = 1; i <= n3; i++)
  61. {
  62. cin >> a[i + n1 + n2].first;
  63. a[i + n1 + n2].second = 2;
  64. }
  65. sort(a.begin() + 1, a.end());
  66.  
  67. for(int i = 1; i <= sz; i++)
  68. {
  69. relax(i);
  70. ll j = a[i].second;
  71. dpsum[i][j]++;
  72. dp2[i][j] = i;
  73. for(int k = 0; k <= 2; k++) dp1[i][j][k] += dpsum[i][k];
  74. }
  75.  
  76. for(int i = 1; i <= sz; i++)
  77. {
  78. for(int j = 0; j <= 2; j++)
  79. {
  80. if(a[i].second != j)
  81. {
  82. int k = 3 ^ a[i].second ^j;
  83. int ind = lower_bound(a.begin() + 1, a.end(), mp(a[i].first + d + 1 , -1)) - a.begin() - 1;
  84. // cout << closest << " " << ind << "\n";
  85. if( dp2[ind][j] < i) continue;
  86. // cout << "zjhskejzhfkja";
  87. ans += 1LL * (dp1[dp2[ind][j]][j][k] - dp1[i][j][k]);
  88. ans -= 1LL * (dpsum[dp2[ind][j]][j] - dpsum[i][j]) * dpsum[i][k];
  89. }
  90. }
  91. }
  92.  
  93. cout << ans << "\n";
  94. }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement