Submission #1350103

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

const int N = 3e5+5;
int a[N];
int l[N], r[N], mn[N], 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, int from){
  // if(x == 5) cout << b << " " << from << endl;
  if(b == -1) return 1e18;
  
  bool is1 = (1ll<<b)&x;
  bool is2 = (1ll<<b)&k;
  
  if(is1){
    if(is2) {
      if(!l[u]) l[u] = C++;
      return getans(x, l[u], b-1, 1); 
    }
    if(!l[u]) l[u] = C++;
    if(!r[u]) r[u] = C++;
    return min(mn[l[u]], getans(x, r[u], b-1, 0));
    
  } else {
    if(!is2) {
      if(!l[u]) l[u] = C++;
      if(!r[u]) r[u] = C++;
      return min(mn[r[u]], getans(x, l[u], b-1, 1));
    }
    
    if(!r[u]) r[u] = C++;
    return getans(x, r[u], b-1, 0);
    
  }
}

// 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);
  
  // for(int i=1; i<=n; i++) cout << a[i] << " ";
  // cout << endl;
  // cout << endl;
  // cout << endl;
  
  array<int, 2> ans = {1, 1};
  for(int i=1; i<=n; i++) {
    add(a[i], i);
    int l = getans(a[i], 0, 40, 0);
    ans = max(ans, {i-l+1, -l});
  }
  cout << (-ans[1])+1 << " " << ans[0]-1;
}

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