Advertisement
sacgajcvs

Untitled

Jul 19th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  1. /*
  2. _____ _ _ _ _
  3. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  4. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  5. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  6. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  7.  
  8. */
  9. #include<bits/stdc++.h>
  10. #define ll long long
  11. #define rep(i,a,b) for(ll int i=a;i<b;i++)
  12. #define vi vector<ll int>
  13. #define all(a) (a).begin(),(a).end()
  14. using namespace std;
  15.  
  16. void solve()
  17. {
  18. ll n,k;
  19. cin>>n>>k;
  20. vi v(n);
  21. rep(i,0,n)
  22. {
  23. cin>>v[i];
  24. }
  25. ll ans=0;
  26. sort(all(v));
  27. rep(i,0,n)
  28. {
  29. ll l=0,r=i-1;
  30. while(l<=r)
  31. {
  32. ll mid=(l+r)/2;
  33. if(abs(v[mid]-v[i])<=k)
  34. r=mid-1;
  35. else
  36. l=mid+1;
  37. }
  38. ans+=i-r-1;
  39. l=i+1;
  40. r=n-1;
  41. while(l<=r)
  42. {
  43. ll mid=(l+r)/2;
  44. if(abs(v[mid]-v[i])<=k)
  45. l=mid+1;
  46. else
  47. r=mid-1;
  48. }
  49. ans+=l-i-1;
  50. }
  51. cout<<ans/2+n;
  52. return;
  53. }
  54. int main()
  55. {
  56. ios_base::sync_with_stdio(false);
  57. cin.tie(0);
  58. cout.tie(0);
  59. int TESTS=1;
  60. // cin>>TESTS;
  61. while(TESTS--)
  62. {
  63. solve();
  64. }
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement