Submission #1350134

#TimeUsernameProblemLanguageResultExecution timeMemory
1350134bakhtiyarnXOR (IZhO12_xor)C++20
0 / 100
1 ms2628 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int inf = 1e18;
const int N = 3e5+5;
int a[N];
int l[N*29], r[N*20], mn[N*20], C = 1;
int n, k;

void add(int x, int i){
  int u = 0;
  for(int b=40; b>=0; b--){
    bool is1 = (1ll<<b)&x;
    if(is1) {
      if(!r[u]) r[u] = C++;
      u = r[u];
    }
    else {
      if(!l[u]) l[u] = C++;
      u = l[u];
    }
    mn[u] = min(mn[u], i);
  }
}

int getans(int x, int u, int b){
  if(b == -1) return 1e18;
  
  bool is1 = (1ll<<b)&x;
  bool is2 = (1ll<<b)&k;
  
  if(is1){
    if(is2) {
      return (l[u] ? getans(x, l[u], b-1) : inf); 
    }
    return min(mn[l[u]], (r[u] ? getans(x, r[u], b-1) : inf));
    
  } else {
    if(!is2) {
      return min(mn[r[u]], (l[u] ? getans(x, l[u], b-1): inf));
    }
    
    return (r[u] ? getans(x, r[u], b-1) : inf);
  }
}

// for(int i=1; i<=n; i++) 
void solve(){
  cin >> n >> k;
  for(int i=1; i<=n; i++) cin >> a[i], a[i] ^= a[i-1];
  for(int i=0; i<N; i++) mn[i] = 1e18;
  add(0, 0);
  
  array<int, 2> ans = {1, 1};
  for(int i=1; i<=n; i++) {
    int l = getans(a[i], 0, 40);
    ans = max(ans, {i-l, -l-1});
    add(a[i], i);
  }
  cout << -ans[1] << " " << ans[0];
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...