fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct trie
  4. {
  5.     long long int val;
  6.     int pos;
  7.     struct trie *left;
  8.     struct trie *right;
  9. };
  10. struct trie *root;
  11. int maxsize = 32;
  12. struct trie *initialise()
  13. {
  14.     struct trie *node;
  15.     node = new trie();
  16.     node->val = -1;
  17.     node->pos = -1;
  18.     node->left = NULL;
  19.     node->right = NULL;
  20.     return node;
  21. };
  22. void insert(long long int n,int m)
  23. {
  24.     struct trie *node;
  25.     node = root;
  26.     int i;
  27.  
  28.     for(i = maxsize - 1; i >= 0; i--) {
  29.         if(n&(1 << i)) {
  30.             if(node->right == NULL) {
  31.                 node->right = initialise();
  32.             }
  33.             node = node->right;
  34.         }
  35.         else {
  36.             if(node->left == NULL) {
  37.                 node->left = initialise();
  38.             }
  39.             node = node->left;
  40.         }
  41.     }
  42.     node->val = n;
  43.     node->pos = m;
  44. }
  45. pair<long long  int,int> query(long long int n)
  46. {
  47.     int i;
  48.     struct trie *node;
  49.     node = root;
  50.  
  51.     for(i = maxsize - 1; i >= 0; i--) {
  52.         if(n & (1 << i)) {
  53.             if(node->left != NULL) {
  54.                 node = node->left;
  55.             }
  56.             else {
  57.                 node = node->right;
  58.             }
  59.         }
  60.         else {
  61.             if(node->right != NULL) {
  62.                 node = node->right;
  63.             }
  64.             else {
  65.                 node = node->left;
  66.             }
  67.         }
  68.     }
  69.  
  70.     return make_pair(node->val,node->pos);
  71. }
  72.  
  73.  
  74.  
  75. int main()
  76. {
  77.     long long int n;
  78.     long long int a[100005];
  79.     int i;
  80.     map<long long int,int> m;
  81.     int l;
  82.     int r;
  83.     pair<long long int,int> t;
  84.     long long int y;
  85.     long long int x;
  86.  
  87.     long long int max;
  88.     int count;
  89.  
  90.  
  91.  
  92.      root = initialise();
  93.     cin>>n; 
  94.     max = -1;
  95.     count = 0;
  96.     for(i = 1; i <= n; i++) {
  97.         cin>>a[i];
  98.  
  99.     }
  100.  
  101.  
  102.  
  103.     insert(0,0);
  104.     m[0] = 1;
  105.  
  106.     x = 0;
  107.  
  108.     for(i = 1; i <= n; i++) {
  109.         x = x ^ a[i];
  110.         if(m[x] == 0) {
  111.          insert(x,i);
  112.          m[x] = 1;
  113.         }
  114.  
  115.  
  116.         t = query(x);
  117.         t.first = t.first ^ x;
  118.         if(t.first > max) {
  119.             max = t.first;
  120.             r = i;
  121.            //cout<<t.second<<endl;
  122.  
  123.             l = t.second + 1;
  124.  
  125.  
  126.         }
  127.     }
  128.     cout<<max<<endl;
  129.     cout<<l<<' '<<r<<endl;
  130.  
  131.  
  132.  
  133. }
  134.  
Success #stdin #stdout 0s 3936KB
comments (?)
stdin
copy 
3
1 2 0
stdout
copy 
3
1 2
https://ideone.com/tGjUdY
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!