fork download
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. int main() {
  5. static int UPPER_LIMIT = 10001;
  6. static int K = 32;
  7. int frequencies[UPPER_LIMIT] = {0}; // O(U)
  8. int n;
  9. std::cin >> n;
  10. for (int i = 0; i < n; i++) { // O(n)
  11. int x;
  12. std::cin >> x;
  13. frequencies[x] += 1;
  14. }
  15. for (int i = 1; i < UPPER_LIMIT; i++) { // O(U)
  16. frequencies[i] += frequencies[i-1];
  17. }
  18. int count = 0;
  19. for (int i = 1; i < UPPER_LIMIT; i++) { // O(U)
  20. int low_idx = std::max(i-32, 0);
  21. int number_of_elements_with_value_i = frequencies[i] - frequencies[i-1];
  22. if (number_of_elements_with_value_i == 0) continue;
  23. int number_of_elements_with_value_K_close_to_i =
  24. (frequencies[i] - frequencies[low_idx]) - 1; // to avoid adding number
  25. // with itself.
  26. std::cout << "i: " << i << " number_of_elements_with_value_i: " << number_of_elements_with_value_i << " number_of_elements_with_value_K_close_to_i: " << number_of_elements_with_value_K_close_to_i << std::endl;
  27. count += number_of_elements_with_value_i * number_of_elements_with_value_K_close_to_i;
  28. }
  29. std::cout << count;
  30. return 0;
  31. }
Success #stdin #stdout 0s 15240KB
stdin
10

5 5 100 102 105 133 200 200 200 200
stdout
i: 5 number_of_elements_with_value_i: 2 number_of_elements_with_value_K_close_to_i: 1
i: 100 number_of_elements_with_value_i: 1 number_of_elements_with_value_K_close_to_i: 0
i: 102 number_of_elements_with_value_i: 1 number_of_elements_with_value_K_close_to_i: 1
i: 105 number_of_elements_with_value_i: 1 number_of_elements_with_value_K_close_to_i: 2
i: 133 number_of_elements_with_value_i: 1 number_of_elements_with_value_K_close_to_i: 2
i: 200 number_of_elements_with_value_i: 4 number_of_elements_with_value_K_close_to_i: 3
19