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
comments (?)
stdin 
5
4 8 2 6 2
4 5 4 1 3
stdout 
7
https://ideone.com/ehre37
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!