output is coming correct on ideone but not on codeforces for the problem http://mirror.codeforces.com/contest/282/problem/E http://ideone.com/VFBY1G
#include<bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
typedef long long LL;
typedef struct ll
{
int leftc; // number of prefixes that end towards left
int rightc;//number of prefixes ending towards right
struct ll * left;
struct ll * right;
}node;
node * insert(node * root,long long n, int level)
{
if(level==-1)return root;
long long x=((n>>level)&1);
if(x)
{
root->rightc++;
if(root->right==NULL)
{
root->right=(node *)malloc(sizeof(node));
root->right->leftc=root->right->rightc=0;
}
root->right=insert(root->right,n,level-1);
}
else
{
root->leftc++;
if(root->left==NULL)
{
root->left=(node *)malloc(sizeof(node));
root->left->leftc=root->left->rightc=0;
}
root->left=insert(root->left,n,level-1);
}
return root;
}
long long arr[50];
long long query( node * root,long long n, int level)
{
if(level==-1 || root==NULL)return 0LL;
long long int p=((n>>level)&1);
if(p){
if(root->left!=NULL){
return query(root->left,n,level-1);
} else {
return query(root->right,n,level-1)+arr[level];
}
} else {
if(root->right!=NULL){
return query(root->right,n,level-1)+arr[level];
} else {
return query(root->left,n,level-1);
}
}
}
node* remove(node *root,long long n,int level)
{
if(level==-1 || root==NULL)return root;
if (n >> level & 1)
{
root->rightc--;
remove(root->right,n,level-1);
if (root->rightc==0) root->right = NULL;
}
else
{
root->leftc--;
remove(root->left,n,level-1);
if (root->leftc==0) root->left = NULL;
}
return root;
}
long long a[100005];
int main()
{
int i,n;
long long int val,xx,ans=0;
node * root;
root=(node *)malloc(sizeof(node));
root->left=root->right=NULL;
root->leftc=root->rightc=0;
arr[0]=1;
for(i=1;i<41;i++){
arr[i]=arr[i-1]*2;
}
//cout<<arr[40]<<endl;
cin>>n;
xx=0;
for(i=0;i<n;i++){
cin>>a[i];
xx=xx^a[i];
root=insert(root,xx,40);
}
//cout<<root->rightc<<" "<<root->leftc<<endl;
xx=0;
for(i=n-1;i>=0;i--){
xx^=a[i];
root=remove(root,a[i],40);
val=query(root,xx,40);
//cout<<xx<<" "<<val<<endl;
ans=max(ans,xx^val);
}
cout<<ans<<endl;
}
simple case like like 2 1 2 is also failing on codeforces can somebody point out the mistake i am using trie for applying addition and removing operations
It seems that your trouble caused because of dynamic allocations.
At least, I feel this code not OK:
What is the value of root->right->left and root->right->right? They are not initialized. malloc function doesn't clear the memory allocated. You may need to use calloc. But the following code is better:
PS: Your trie code is too long, you may need to reduce its length.
ya the problem was with malloc got ac thanx