Submission #589140

# Submission time Handle Problem Language Result Execution time Memory
589140 2022-07-04T09:39:00 Z Mamedov XOR (IZhO12_xor) C++17
100 / 100
320 ms 143784 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 11 ms 3908 KB Output is correct
6 Correct 16 ms 4428 KB Output is correct
7 Correct 15 ms 4408 KB Output is correct
8 Correct 20 ms 4584 KB Output is correct
9 Correct 132 ms 67504 KB Output is correct
10 Correct 129 ms 67876 KB Output is correct
11 Correct 125 ms 67460 KB Output is correct
12 Correct 124 ms 67628 KB Output is correct
13 Correct 123 ms 67784 KB Output is correct
14 Correct 121 ms 67864 KB Output is correct
15 Correct 128 ms 67868 KB Output is correct
16 Correct 129 ms 67700 KB Output is correct
17 Correct 320 ms 143496 KB Output is correct
18 Correct 309 ms 143784 KB Output is correct
19 Correct 292 ms 143696 KB Output is correct
20 Correct 314 ms 143608 KB Output is correct