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. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. // Ký hiệu: x - giá trị lớn nhất
  17. //          y - giá trị lớn nhì
  18. // Đây là một bài với ý tưởng khá educational
  19. // Ta sẽ thử cho từng a(i) làm giá trị y
  20. // Gọi l(i) = phần tử gần nhất bên trái > a(i) 
  21. //     r(i) = phần tử gần nhất bên phải > a(i)
  22. // Ta có l(i), a(i) lần lượt là x, y của đoạn [l(i), a[i]]
  23. // Tương tự ta cũng có r(i), a(i) lần lượt là x, y của đoạn [a[i], r[i]]
  24. // Bằng cách này ta có thể duyệt qua được mọi cặp x, y của mọi đoạn có thể có
  25. const int N = 1e5 + 5; 
  26.  
  27. int n; 
  28. int a[N]; 
  29.  
  30. int l[N]; 
  31. int r[N];
  32.  
  33. int main() {
  34. 	ios::sync_with_stdio(false); 
  35. 	cin.tie(nullptr); 	
  36. 	cin >> n; 
  37. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  38.  
  39. 	vector<int> st; 
  40. 	for (int i = 1; i <= n; i++) {
  41. 		while (!st.empty() && a[st.back()] <= a[i]) st.pop_back(); 
  42. 		l[i] = st.empty() ? 0 : st.back(); 
  43. 		st.push_back(i); 
  44. 	}
  45.  
  46. 	st.clear();  
  47. 	for (int i = n; i >= 1; i--) {
  48. 		while (!st.empty() && a[st.back()] <= a[i]) st.pop_back(); 
  49. 		r[i] = st.empty() ? n + 1 : st.back(); 
  50. 		st.push_back(i); 
  51. 	}
  52.  
  53. 	int ans = 0; 
  54. 	for (int i = 1; i <= n; i++) {
  55. 		if (l[i] > 0) maximize(ans, a[l[i]] ^ a[i]);  
  56. 		if (r[i] <= n) maximize(ans, a[r[i]] ^ a[i]);
  57. 	}
  58.  
  59. 	cout << ans << '\n'; 
  60. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
5
5 2 1 4 3
stdout
copy 
7
https://ideone.com/HGz72s
language:
C++14 (gcc 8.3)
created:
256 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!