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 = 5e5 + 5; 
  11.  
  12. struct info {
  13. 	int B, I, R; 
  14. 	bool operator<(const info& other) const {
  15. 		return (B > other.B); 
  16. 	}
  17. };  
  18.  
  19. int n;  
  20. info a[N]; 
  21.  
  22. void compress_I(info a[]) {
  23. 	vector<int> vals;  
  24. 	for (int i = 1; i <= n; i++) vals.push_back(a[i].I); 
  25.  
  26. 	sort(vals.begin(), vals.end()); 
  27. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  28.  
  29. 	for (int i = 1; i <= n; i++) {
  30. 		a[i].I = lower_bound(vals.begin(), vals.end(), a[i].I) - vals.begin() + 1; 
  31. 	}
  32. }
  33.  
  34. int ft[N]; 
  35.  
  36. void update(int i, int val) {
  37. 	for (; i > 0; i -= i & (-i)) ft[i] = max(ft[i], val); 
  38. }
  39.  
  40. int get(int i) {
  41. 	int ans = 0; 
  42. 	for (; i <= n; i += i & (-i)) ans = max(ans, ft[i]); 
  43. 	return ans; 
  44. }
  45.  
  46. int main() {
  47. 	ios::sync_with_stdio(0); cin.tie(0);  	
  48. 	cin >> n; 
  49. 	for (int i = 1; i <= n; i++) cin >> a[i].B; 
  50. 	for (int i = 1; i <= n; i++) cin >> a[i].I; 
  51. 	for (int i = 1; i <= n; i++) cin >> a[i].R; 
  52.  
  53. 	sort(a + 1, a + n + 1); 
  54.  
  55. 	// int ans = 0;   
  56. 	// for (int i = 1; i <= n; i++) {
  57. 	// 	int max_R = -1; 
  58. 	// 	for (int j = 1; j < i; j++) {
  59. 	// 		if (a[j].B > a[i].B && a[j].I > a[i].I) max_R = max(max_R, a[j].R); 
  60. 	// 	}
  61. 	// 	ans += (max_R > a[i].R);
  62. 	// }
  63.  
  64. 	compress_I(a);
  65.  
  66. 	int ans = 0;  
  67. 	for (int i = 1; i <= n; ) {
  68. 		// tính đáp án cho block a[i].B
  69. 		int j = i; 
  70. 		while (j <= n && a[j].B == a[i].B) {
  71. 			// max_a[k].R của những thằng k ở trước sao cho a[k].I nằm trong đoạn [a[j].I + 1, n]
  72. 			int max_R = get(a[j].I + 1); 
  73. 			ans += (max_R > a[j].R); 
  74. 			j++; 
  75. 		}
  76.  
  77. 		// update block hiện tại vào BIT
  78. 		j = i;  
  79. 		while (j <= n && a[j].B == a[i].B) {
  80. 			update(a[j].I, a[j].R); 
  81. 			j++; 
  82. 		}
  83.  
  84. 		// nhảy sang block tiếp theo 
  85. 		i = j; 
  86. 	}
  87.  
  88. 	cout << ans << '\n'; 
  89. }
Success #stdin #stdout 0.01s 5652KB
comments (?)
stdin
copy 
3
1 4 2
4 3 2
2 5 3
stdout
copy 
1
https://ideone.com/5cSgG4
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!