jiteshrao

Untitled

Oct 11th, 2020 (edited)
86
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. class Node
  7. {
  8. public:
  9.     Node * child[2];
  10.     Node()
  11.     {
  12.         child[0] = NULL;
  13.         child[1] = NULL;
  14.     }
  15. };
  16.  
  17. // time complexity  = N * log2(max(A[i]))
  18.  
  19. void insert(Node * root, int x)
  20. {
  21.     for(int i = 32; i >= 0; i--)
  22.     {
  23.         int bit = ((x >> i) & 1);
  24.         if(root -> child[bit] == NULL)
  25.         {
  26.             root -> child[bit] = new Node();
  27.         }
  28.         root = root -> child[bit];
  29.     }
  30. }
  31.  
  32. //time complexity  = N * log2(max(A[i]))
  33.  
  34. int maXxor(Node * root, int y)
  35. {
  36.     int ret = 0;
  37.     for(int i = 32; i >= 0; i--)
  38.     {
  39.         int bit = ((y >> i) & 1);
  40.         if(root -> child[bit ^ 1] == NULL)
  41.         {
  42.             root = root -> child[bit];
  43.         }
  44.         else
  45.         {
  46.             ret |= (1LL << i);
  47.             root = root -> child[bit ^ 1];
  48.         }
  49.     }
  50.     return ret;
  51. }
  52.  
  53. // space complexity is nlogn;
  54.  
  55. int32_t main()
  56. {
  57.     int n;
  58.     cin >> n;
  59.     vector<int> arr(n);
  60.     Node * root = new Node();
  61.     int ans = 0;
  62.     int prefix = 0;
  63.     insert(root, 0);
  64.     for(int i = 0; i < n; i++)
  65.     {
  66.         cin >> arr[i];
  67.         prefix ^= arr[i];
  68.         insert(root, prefix);
  69.         int temp = maXxor(root, prefix);
  70.         ans = max(ans, temp);
  71.     }
  72.     cout << ans << endl;
  73. }
RAW Paste Data