fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define sd(n) scanf("%d",&n)
  4. typedef long long LL;
  5. typedef struct ll
  6. {
  7.     int leftc; // number of prefixes that end towards left
  8.     int rightc;//number of prefixes ending towards right
  9.     struct ll * left;
  10.     struct ll * right;
  11. }node;
  12. node * insert(node * root,long long n, int level)
  13. {
  14.     if(level==-1)return root;
  15.     long long x=((n>>level)&1);
  16.     if(x)
  17.     {
  18.         root->rightc++;
  19.         if(root->right==NULL)
  20.         {
  21.             root->right=(node *)malloc(sizeof(node));
  22.             root->right->leftc=root->right->rightc=0;
  23.         }
  24.         root->right=insert(root->right,n,level-1);
  25.     }
  26.     else
  27.     {
  28.         root->leftc++;
  29.         if(root->left==NULL)
  30.         {
  31.             root->left=(node *)malloc(sizeof(node));
  32.             root->left->leftc=root->left->rightc=0;
  33.         }
  34.         root->left=insert(root->left,n,level-1);
  35.     }
  36.     return root;
  37. }
  38. long long arr[50];
  39. long long query( node * root,long long  n, int level)
  40. {
  41.     if(level==-1 || root==NULL)return 0LL;
  42.     long long int p=((n>>level)&1);
  43.     if(p){
  44. 	if(root->left!=NULL){	
  45. 		return query(root->left,n,level-1);
  46. 	} else {
  47. 		return query(root->right,n,level-1)+arr[level];
  48. 	}
  49.     } else {
  50. 	if(root->right!=NULL){	
  51. 		return query(root->right,n,level-1)+arr[level];
  52. 	} else {
  53. 		return query(root->left,n,level-1);
  54. 	}
  55.     }
  56. }
  57. node* remove(node *root,long long n,int level)
  58. {
  59. 		if(level==-1 || root==NULL)return root;
  60. 		if (n >> level & 1)
  61. 		{
  62. 			root->rightc--;
  63. 			remove(root->right,n,level-1);
  64. 			if (root->rightc==0) root->right = NULL;
  65. 		}
  66. 		else
  67. 		{
  68. 			root->leftc--;
  69. 			remove(root->left,n,level-1);
  70. 			if (root->leftc==0) root->left = NULL;
  71. 		}
  72. 		return root;
  73. }
  74. long long a[100005];
  75. int main()
  76. {
  77.      int i,n;
  78.      long long int val,xx,ans=0;
  79.      node * root;
  80.      root=(node *)malloc(sizeof(node));
  81.      root->left=root->right=NULL;
  82.      root->leftc=root->rightc=0;
  83.      arr[0]=1;
  84.      for(i=1;i<41;i++){
  85. 	     arr[i]=arr[i-1]*2;
  86.      }
  87.      //cout<<arr[40]<<endl;
  88.     cin>>n;
  89.     xx=0;
  90.     for(i=0;i<n;i++){
  91. 		cin>>a[i];
  92. 		xx=xx^a[i];
  93. 		root=insert(root,xx,40);
  94.     }
  95.  
  96. 	//cout<<root->rightc<<" "<<root->leftc<<endl;
  97.    xx=0;
  98.    //root=remove(root,a[n-1],40);
  99.   // traverse(root);
  100.    for(i=n-1;i>=0;i--){
  101.      xx^=a[i];
  102.      root=remove(root,a[i],40);
  103.      val=query(root,xx,40);
  104.     //cout<<xx<<" "<<val<<endl;
  105.      ans=max(ans,xx^val);
  106.      }
  107.  
  108.    cout<<ans<<endl;
  109. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin 
6
13 21 3 61 1 2
stdout 
39
https://ideone.com/VFBY1G
language:
C++ (gcc 8.3)
created:
10 years 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!