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 = 1e5 + 5; 
  11.  
  12. struct domino {
  13. 	int x, h, pos;  
  14. 	bool operator<(const domino& other) const {
  15. 		return (x < other.x);
  16. 	}
  17. }; 
  18.  
  19. int n; 
  20. domino a[N];  
  21.  
  22. int seg[4 * N]; 
  23.  
  24. void update(int id, int l, int r, int pos, int val) {
  25. 	if (l > pos || r < pos) return; 
  26.  
  27. 	if (l == r) {
  28. 		seg[id] = val; 
  29. 		return; 
  30. 	}
  31.  
  32. 	int mid = (l + r) >> 1; 
  33. 	update(id * 2, l, mid, pos, val); 
  34. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  35.  
  36. 	seg[id] = max(seg[id * 2], seg[id * 2 + 1]); 
  37. }
  38.  
  39. int getMax(int id, int l, int r, int u, int v) {
  40. 	if (l > v || r < u) return -INF;  
  41.  
  42. 	if (u <= l && r <= v) return seg[id]; 
  43.  
  44. 	int mid = (l + r) >> 1; 
  45. 	return max(getMax(id * 2, l, mid, u, v), getMax(id * 2 + 1, mid + 1, r, u, v)); 
  46. }
  47.  
  48. // Tìm i đầu tiên trong đoạn [l, r] sao cho a[i].x > x
  49. int binSearch(domino a[], int l, int r, int x) {
  50. 	int ans = r + 1;  
  51. 	while (l <= r) {
  52. 		int mid = (l + r) >> 1; 
  53. 		if (a[mid].x > x) {
  54. 			ans = mid;   
  55. 			r = mid - 1; 
  56. 		}
  57. 		else {
  58. 			l = mid + 1; 
  59. 		}
  60. 	}
  61. 	return ans; 
  62. }
  63.  
  64. int dp[N]; // dp[i] = số domino sẽ bị đổ nếu ta đổ domino thứ i 
  65. int ans[N];  
  66.  
  67. int main() {
  68. 	ios::sync_with_stdio(0); cin.tie(0);  	
  69. 	cin >> n; 
  70. 	for (int i = 1; i <= n; i++) {
  71. 		cin >> a[i].x >> a[i].h;  
  72. 		a[i].pos = i;  
  73. 	}
  74.  
  75. 	sort(a + 1, a + n + 1);  
  76.  
  77. 	//     dp[i] = max{(j - i) + dp[j]} 
  78. 	// <=> dp[i] = max{dp[j] + j} - i  
  79.  
  80. 	for (int i = n; i >= 1; i--) {
  81. 		dp[i] = 1;   
  82.  
  83. 		// [l, r] là đoạn các domino có thể bị đổ trực tiếp bởi domino i
  84. 		int l = binSearch(a, i + 1, n, a[i].x); 
  85. 		int r = binSearch(a, i + 1, n, a[i].x + a[i].h - 1) - 1; 
  86.  
  87. 		if (l <= r) {
  88. 			dp[i] = getMax(1, 1, n, l, r) - i; 
  89. 		}
  90.  
  91. 		update(1, 1, n, i, dp[i] + i); 
  92. 	}
  93.  
  94. 	for (int i = 1; i <= n; i++) ans[a[i].pos] = dp[i]; 
  95.  
  96. 	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';  
  97. }
Success #stdin #stdout 0.01s 5604KB
comments (?)
stdin
copy 
4
0 10
1 5
9 10
15 10
stdout
copy 
4 1 2 1
https://ideone.com/HrZ3Nv
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!