fork(4) download
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. ll n, x, k;
  8. ll a[100100];
  9. ll ans;
  10.  
  11. ll solve(ll le, ll ri)
  12. {
  13. if (le > a[n - 1] || ri < a[0])
  14. return 0;
  15. ll res = 0;
  16. int l = 0;
  17. int r = n - 1;
  18. int m;
  19. while (r - l > 1)
  20. {
  21. m = (l + r) / 2;
  22. if (a[m] >= le)
  23. r = m;
  24. else
  25. l = m;
  26. }
  27. if (a[l] >= le)
  28. m = l;
  29. else
  30. m = r;
  31. res = m;
  32. l = 0;
  33. r = n - 1;
  34. while (r - l > 1)
  35. {
  36. m = (l + r) / 2;
  37. if (a[m] <= ri)
  38. l = m;
  39. else
  40. r = m;
  41. }
  42. if (a[r] <= ri)
  43. m = r;
  44. else
  45. m = l;
  46. return m - res + 1;
  47. }
  48.  
  49. int main()
  50. {
  51. cin >> n >> x >> k;
  52. for (int i = 0; i < n; i++)
  53. cin >> a[i];
  54. sort(a, a + n);
  55. for (int i = 0; i < n; i++)
  56. {
  57. ll y = a[i] - 1;
  58. y /= x;
  59. ll le = max(x*(k + y), a[i]);
  60. ll ri = x*(k + y + 1) - 1;
  61. ans += solve(le, ri);
  62. }
  63. cout << ans << endl;
  64. }
Success #stdin #stdout 0s 16848KB
stdin
Standard input is empty
stdout
0