This is my code:
#include
#include
using namespace std;
class node
{
public:
node* left;
node* right;
pair<long int, long int> p;
node()
{
left = NULL;
right = NULL;
p.first = 0;
p.second = 0;
}
};
class trie
{
node* root;
public:
trie()
{
root = new node();
root->p.first = 1;
}
void insert(long long int x, long int pos)
{
node* temp = root;
root->p.second = pos;
for (int i = ((sizeof(x) * 8) - 1); i >= 0; i–)
{
int a = (x >> i) & 1;
if (a)
{
if (!temp->right)
{
temp->right = new node();
}
temp = temp->right;
}
else
{
if (!temp->left)
{
temp->left = new node();
}
temp = temp->left;
}
if (temp->p.first == 0)
{
temp->p.first = pos;
temp->p.second = pos;
}
else
{
temp->p.second = pos;
}
}
return;
}
long long int max_xor(long int l, long int r, long long int x)
{
node* temp = root;
long long int max = 0;
for (int i = ((sizeof(x) * 8) - 1); i >= 0; i–)
{
int a = (x >> i) & 1;
if (a)
{
if (temp->left and (temp->left->p.first <= r and temp->left->p.second >= l))
{
temp = temp->left;
}
else
{
temp = temp->right;
max += (1 << i);
}
}
else
{
if (temp->right and (temp->right->p.first <= r and temp->right->p.second >= l))
{
temp = temp->right;
max += (1 << i);
}
else
{
temp = temp->left;
}
}
}
return max;
}
};
int main()
{
long int q = 0;
cin >> q;
trie t;
long int pos = 1;
for (long int i = 0; i < q; i++)
{
int type = 0;
cin >> type;
if (type)
{
long int l = 0, r = 0;
long long int x = 0;
cin >> l >> r;
cin >> x;
cout << t.max_xor(l, r, x) << endl;
}
else
{
long long int x = 0;
cin >> x;
t.insert(x, pos);
pos++;
}
}
}
Only one test case passed, one is wrong and the third one shows MLE. Please help