fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fst first
  5. #define snd second
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> ii;
  9.  
  10. const ll LINF = (ll)1e18;
  11. const int INF = (int)1e9;
  12.  
  13. const int N = (int)2e5 + 5;
  14.  
  15. // Đếm số cặp (i, j) (i < j) sao cho a[i] + a[j] > b[i] + b[j]
  16. // <=> a[i] - b[i] > b[j] - a[j]
  17. // Nên ở đây các em có thể tạo 1 mảng c chứa các giá trị b[j] - a[j], sort c tăng dần
  18. // Sau đó với mỗi i ở mảng a thì ta đếm có bao nhiêu j ở c thoả mãn c[j] < a[i] - b[i]
  19.  
  20. int n, a[N], b[N];
  21.  
  22. int main() {
  23. ios::sync_with_stdio(0);
  24. cin.tie(0);
  25. cin >> n;
  26. for (int i = 1; i <= n; i++) cin >> a[i];
  27.  
  28. vector<int> c;
  29. for (int i = 1; i <= n; i++) {
  30. cin >> b[i];
  31. c.push_back(b[i] - a[i]);
  32. }
  33.  
  34. sort(c.begin(), c.end());
  35.  
  36. ll cnt = 0;
  37. for (int i = 1; i <= n; i++) {
  38. // vị trí j lớn nhất sao cho c[j] < x
  39. // = (vị trí j' đầu tiên sao cho c[j] >= x) - 1
  40. cnt += (lower_bound(c.begin(), c.end(), a[i] - b[i]) - c.begin() - 1) + 1; // vì mảng c đánh số từ 0
  41. cnt -= (b[i] - a[i] < a[i] - b[i]); // nhớ trừ trường hợp i = j
  42. }
  43.  
  44. cout << cnt / 2 << '\n'; // Mỗi cặp (i, j) bị đếm lặp 2 lần
  45. }
Success #stdin #stdout 0.01s 5272KB
stdin
5
4 8 2 6 2
4 5 4 1 3
stdout
7