Advertisement
newb_ie

bs4

Sep 1st, 2021
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxN = 2e5 + 100;
  5. long long a[maxN];
  6.  
  7. int find_min_idx (long long L,int n,long long x) {
  8. //a[m] >= L
  9. int l = 1,r = n;
  10. int res = -1;
  11. while (l <= r) {
  12. int m = (l + r) / 2;
  13. if (a[m] + x >= L) {
  14. res = m;
  15. r = m - 1;
  16. } else {
  17. l = m + 1;
  18. }
  19. }
  20. return res;
  21. }
  22.  
  23. int find_max_idx (long long R,int n,long long x) {
  24. //a[m] <= R
  25. int l = 1,r = n;
  26. int res = -1;
  27. while (l <= r) {
  28. int m = (l + r) / 2;
  29. if (a[m] + x <= R) {
  30. res = m;
  31. l = m + 1;
  32. } else {
  33. r = m - 1;
  34. }
  35. }
  36. return res;
  37. }
  38.  
  39. int main () {
  40. ios::sync_with_stdio(false);
  41. cin.tie(nullptr);
  42. cout.tie(nullptr);
  43. int T;
  44. cin >> T;
  45. for (int test_case = 1; test_case <= T; ++test_case) {
  46. long long n,L,R;
  47. cin >> n >> L >> R;
  48. for (int i = 1; i <= n; ++i) cin >> a[i];
  49. sort (a + 1,a + n + 1);
  50. long long res = 0;
  51. for (int i = 1; i <= n; ++i) {
  52. int l = find_min_idx(L,i - 1,a[i]);
  53. int r = find_max_idx(R,i - 1,a[i]);
  54. if (l == -1 or r == -1 or l > r) {
  55. continue;
  56. }
  57. res += (r - l + 1);
  58. }
  59. cout << res << '\n';
  60. }
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement