Submission #589140

#	Time	Username	Problem	Language	Result	Execution time	Memory
589140		Mamedov	XOR (IZhO12_xor)	C++17	100 / 100	320 ms	143784 KiB

xor

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Trie {
  int val;
  vector<Trie*>link;
  Trie(int v): val(v), link(vector<Trie*>(2, nullptr)) {}
  void add(int num, int id) {
    Trie *node = this;
    for (int i = 30; i >= 0; --i) {
      int bit = ((num >> i) & 1);
      if (node->link[bit]) {
        node = node->link[bit];
        node->val = id;
      } else {
        node = node->link[bit] = new Trie(id);
      }
    }
  }
  int findBestr(int l, int x) {
    Trie *node = this;
    int bestr = -1;
    for (int i = 30; i >= 0; --i) {
      int bitl = ((l >> i) & 1);
      int bitx = ((x >> i) & 1);
      if (bitx) {
        if (node->link[bitl ^ 1]) {
          node = node->link[bitl ^ 1];
        } else {
          return bestr;
        }
      } else {
        if (node->link[bitl ^ 1]) {
          bestr = max(bestr, node->link[bitl ^ 1]->val);
        }
        if (node->link[bitl]) {
          if (node->link[bitl]->val > bestr) {
            node = node->link[bitl];
          } else {
            return bestr;
          }
        }
      }
    }
    bestr = max(bestr, node->val);
    return bestr;
  }
};
void solve() {
  int n, x;
  cin >> n >> x;
  vector<int>p(n + 1);
  p[0] = 0;
  Trie *root = new Trie(0);
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    p[i] ^= p[i - 1];
    root->add(p[i], i);
  }
  int l = 0, len = 0;
  for (int i = 0; i < n; ++i) {
    int bestr = root->findBestr(p[i], x);
    if (bestr - i > len) {
      len = bestr - i;
      l = i + 1;
    }
  }
  cout << l << ' ' << len << ln;
}
int main() {
  ios_base::sync_with_stdio(false);
  solve();
  return 0;
}

• Subtask 1: 100 / 100