fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11.  
  12. struct segment {
  13. 	int x, y, i; 
  14.  
  15. }; 
  16.  
  17. // có một số kiểu truyền tham số: 
  18. // - truyền bằng tham trị: pass by value (int x): tốn thêm bộ nhớ để tạo ra bản sao của x 
  19. // - truyền bằng tham chiếu: pass by reference (int& x): dùng bản gốc 
  20. // - hằng tham chiếu (const int& x): dùng bản gốc, không được phép thay đổi giá trị của x
  21.  
  22. bool cmp_y(const segment& a, const segment& b) {
  23. 	if (a.y == b.y) {
  24. 		return (a.x > b.x); 
  25. 	}
  26. 	return (a.y < b.y); 
  27. }
  28.  
  29. bool cmp_x(const segment& a, const segment& b) {
  30. 	if (a.x == b.x) {
  31. 		return (a.y > b.y); 
  32. 	}
  33. 	return (a.x < b.x); 
  34. }
  35.  
  36. int n;  
  37. segment a[N], b[N]; 
  38. int ft[N]; 
  39.  
  40. void init() {
  41. 	for (int i = 1; i <= n; i++) ft[i] = 0;  
  42. }
  43.  
  44. void update(int i, int val) {
  45. 	for (; i > 0; i -= i & (-i)) ft[i] += val; 
  46. }
  47.  
  48. int get(int i) {
  49. 	int ans = 0;  
  50. 	for (; i <= n; i += i & (-i)) ans += ft[i];
  51. 	return ans; 
  52. }
  53.  
  54. int ans[N]; 
  55.  
  56. // Mỗi đoạn thẳng [x[i], y[i]] chứa bao nhiêu đoạn thẳng [x[j], y[j]]
  57. void sub1() {
  58. 	// y(j) <= y(i), x(j) >= x(i)
  59. 	// sort tăng dần theo y, cùng y thì giảm dần theo x 
  60. 	sort(a + 1, a + n + 1, cmp_y); 
  61.  
  62. 	// nén x
  63. 	vector<int> vals;  
  64. 	for (int i = 1; i <= n; i++) vals.push_back(a[i].x); 
  65. 	sort(vals.begin(), vals.end()); 
  66. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  67.  
  68.  	// đếm
  69.  	init();
  70.  
  71. 	for (int i = 1; i <= n; i++) {
  72. 		// x(j) >= x(i)
  73. 		// giá trị nén của x(i)
  74. 		int val_x = lower_bound(vals.begin(), vals.end(), a[i].x) - vals.begin() + 1;
  75. 		ans[a[i].i] = get(val_x);   
  76. 		update(val_x, 1); 
  77. 	}
  78.  
  79. 	for (int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << '\n'; 
  80. }
  81.  
  82. // Mỗi đoạn thẳng [x[i], y[i]] bị bao nhiêu đoạn thẳng [x[j], y[j]] chứa
  83. void sub2() {
  84. 	// x(j) <= x(i), y(j) >= y(i)
  85. 	// sort tăng dần theo x, cùng x thì giảm dần theo y 
  86. 	sort(a + 1, a + n + 1, cmp_x); 
  87.  
  88. 	// nén y 
  89. 	vector<int> vals;  
  90. 	for (int i = 1; i <= n; i++) vals.push_back(a[i].y); 
  91. 	sort(vals.begin(), vals.end()); 
  92. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  93.  
  94. 	// đếm
  95. 	init();  
  96.  
  97. 	for (int i = 1; i <= n; i++) {
  98. 		// y(j) >= y(i)
  99. 		// giá trị nén của y(i)
  100. 		int val_y = lower_bound(vals.begin(), vals.end(), a[i].y) - vals.begin() + 1;
  101. 		ans[a[i].i] = get(val_y);   
  102. 		update(val_y, 1); 
  103. 	}
  104.  
  105. 	for (int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << '\n'; 
  106. }
  107.  
  108. int main() {
  109. 	ios::sync_with_stdio(0); cin.tie(0);  	
  110. 	cin >> n; 
  111. 	for (int i = 1; i <= n; i++) {
  112. 		cin >> a[i].x >> a[i].y;
  113. 		a[i].i = i;  
  114. 	}
  115.  
  116. 	sub1();
  117. 	sub2(); 
  118. }
Success #stdin #stdout 0.01s 7808KB
comments (?)
stdin
copy 
4
1 6
2 4
4 8
3 6
stdout
copy 
2 0 0 0 
0 1 0 1
https://ideone.com/EwqKWM
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!