fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. // - Đếm số cặp (x, y) sao cho sum{|x - x(i)| + |y - y(i)|} <= d
  12. // - Từ giới hạn đề cho ta có thể tính ra được -2e6 <= x, y <= 2e6
  13. // - Nhận xét: Ta có thể biến đổi tổng trên thành sum{|x - x(i)|} + sum{|y - y(i)|} <= d
  14. //   Từ đó, đặt val_x(x) = sum{|x - x(i)|}, val_y(y) = sum{|y - y(i)|}
  15. // 	 => Bài toán quy về đếm số cặp (x, y) sao cho val_x(x) + val_y(y) <= d
  16. // - Ta có thể tính trước val_x(x) cho mọi x với -2e6 <= x <= 2e6 (binary search/2 pointers, prefix sum,...) 
  17. //   Tương tự với val_y(y) cho mọi y với -2e6 <= y <= 2e6
  18. // - Sau khi đã có val_x(x), val_y(y) thì bài toán còn lại cũng có thể giải quyết đơn giản bằng binary search/2 pointers, prefix sum,...
  19.  
  20. const int N = 2e5 + 5; 
  21. const int D = 1e6 + 5; 
  22.  
  23. int n, d;  
  24. int x[N], y[N]; 
  25. ll pref_x[N], pref_y[N];
  26. int cnt_x[D]; // cnt_x[i] = Số giá trị x thoả mãn val_x(x) <= i
  27.  
  28. int main() {
  29. 	ios::sync_with_stdio(false); 
  30. 	cin.tie(nullptr); 	
  31. 	cin >> n >> d;
  32. 	for (int i = 1; i <= n; i++) {
  33. 		cin >> x[i] >> y[i]; 
  34. 	}
  35. 	sort(x + 1, x + n + 1);  
  36. 	sort(y + 1, y + n + 1);  
  37.  
  38. 	for (int i = 1; i <= n; i++) {
  39. 		pref_x[i] = pref_x[i - 1] + x[i]; 
  40. 		pref_y[i] = pref_y[i - 1] + y[i]; 	
  41. 	}
  42.  
  43. 	for (int cx = -2e6, i = 0; cx <= 2e6; cx++) {
  44. 		while (i < n && x[i + 1] <= cx) i++;   
  45. 		int cnt_lo = i, cnt_hi = n - i;   
  46. 		ll sum_lo = pref_x[i], sum_hi = pref_x[n] - sum_lo;
  47. 		ll val_x = (1ll * cnt_lo * cx - sum_lo) + (sum_hi - 1ll * cnt_hi * cx); 
  48. 		if (val_x <= d) cnt_x[val_x]++; 
  49. 	}
  50. 	for (int val_x = 1; val_x <= d; val_x++) cnt_x[val_x] += cnt_x[val_x - 1]; 
  51.  
  52. 	ll ans = 0;  
  53. 	for (int cy = -2e6, i = 0; cy <= 2e6; cy++) {
  54. 		while (i < n && y[i + 1] <= cy) i++;   
  55. 		int cnt_lo = i, cnt_hi = n - i;   
  56. 		ll sum_lo = pref_y[i], sum_hi = pref_y[n] - sum_lo;
  57. 		ll val_y = (1ll * cnt_lo * cy - sum_lo) + (sum_hi - 1ll * cnt_hi * cy); 
  58. 		if (val_y <= d) ans += cnt_x[d - val_y]; 
  59. 	}
  60.  
  61. 	cout << ans << '\n'; 
  62. }
Success #stdin #stdout 0.02s 5640KB
comments (?)
stdin
copy 
2 3
0 0
1 0
stdout
copy 
8
https://ideone.com/U6fNKT
language:
C++14 (gcc 8.3)
created:
158 days 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!