Submission #1017194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017194		ind1v	XOR (IZhO12_xor)	C++11	100 / 100	103 ms	90408 KiB

xor

#include <bits/stdc++.h>

using namespace std;

const int N = 250005;
const int L = 30;

int n, x;

struct trie {
  struct node {
    int nxt[2];
    int mn;
    
    node() {
      memset(nxt, -1, sizeof(nxt));
      mn = 1e9;
    }
  } t[L * N];
  int nd = 0;
  
  int new_node() {
    nd++;
    return nd;
  }
  
  trie() {
    new_node();
  }
  
  int que(int v) {
    int p = 1;
    int mn = 1e9;
    for (int i = L - 1; i >= -1; i--) {
      if (i == -1) {
        mn = min(mn, t[p].mn);
        break;
      }
      int j = (v >> i & 1);
      int bit = (x >> i & 1);
      if (bit == 0) {
        if (j > (x >> i & 1)) {
          if (t[p].nxt[0] != -1) {
            mn = min(mn, t[t[p].nxt[0]].mn);
          }
          if (t[p].nxt[1] != -1) {
            p = t[p].nxt[1];
          } else {
            break;
          }
        }
        if ((1 ^ j) > (x >> i & 1)) {
          if (t[p].nxt[1] != -1) {
            mn = min(mn, t[t[p].nxt[1]].mn);
          }
          if (t[p].nxt[0] != -1) {
            p = t[p].nxt[0];
          } else {
            break;
          }
        }
      } else if (bit == 1) {
        if (t[p].nxt[j ^ 1] != -1) {
          p = t[p].nxt[j ^ 1];
        } else {
          break;
        }
      }
    }
    return mn;
  }
  
  void add(int v, int y) {
    int p = 1;
    for (int i = L - 1; i >= 0; i--) {
      int j = (v >> i & 1);
      if (t[p].nxt[j] == -1) {
        t[p].nxt[j] = new_node();
      }
      t[t[p].nxt[j]].mn = min(t[t[p].nxt[j]].mn, y);
      p = t[p].nxt[j];
    }
  }
};

trie tr;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> x;
  int xr = 0;
  tr.add(0, 0);
  int al = -1, ar = -1, ln = -1e9;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    xr ^= a;
    int l = tr.que(xr);
    if (i - l > ln) {
      al = l + 1;
      ar = i;
      ln = i - l;
    }
    tr.add(xr, i);
  }
  cout << al << ' ' << ar - al + 1 << '\n';
  return 0;
}

• Subtask 1: 100 / 100