fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // #define int long long
  6. #define fi first
  7. #define se second
  8. #define siz(x) (int)(x.size())
  9. const int maxN=2e5+5;
  10. int lg2(const int &x){return 31 - __builtin_clz(x);}
  11.  
  12. int n, k, m, cur_trie=0, mx[maxN], nxt[maxN][2], a[maxN];
  13.  
  14. void add(int s, int id)
  15. {
  16.     int last_id=0;
  17.     for(int i=lg2(s); i>=0; i-=1)
  18.     {
  19.         int xet=(1<<i)&s; if(xet) xet=1;
  20.         if(nxt[last_id][xet]==-1)
  21.         {
  22.             cur_trie++;
  23.             nxt[last_id][xet]=cur_trie;
  24.         }
  25.         mx[nxt[last_id][xet]]=max(id, mx[nxt[last_id][xet]]);
  26.         last_id=nxt[last_id][xet];
  27.     }
  28. }
  29.  
  30. int query(int s)
  31. {
  32.     int last_id=0, res=-1;
  33.     for(int i=lg2(k); i>=0; i-=1)
  34.     {
  35.         int xet=(1<<i)&s, xet_k=(1<<i)&k;
  36.         if(xet) xet=1;
  37.         if(xet_k) xet_k=1;
  38.         if(xet_k)
  39.         {
  40.             last_id=nxt[last_id][xet^1];
  41.         }
  42.         else
  43.         {
  44.             if(nxt[last_id][xet^1]!=-1) res=max(res, mx[nxt[last_id][xet^1]]);
  45.             last_id=nxt[last_id][xet];
  46.         }
  47.         if(last_id==-1)
  48.         {
  49.             return res;
  50.         }
  51.     }
  52.     return res;
  53. }
  54.  
  55. void solve()
  56. {
  57.     int ans = -1;
  58.     for(int i=1; i<=n; i+=1)
  59.     {
  60.         add(a[i], i);
  61.         if(query(a[i])==-1) continue;
  62.         else ans=max(ans, i-query(a[i])+1);
  63.     }
  64.     cout<<ans<<'\n';
  65. }
  66.  
  67. int32_t main()
  68. {
  69.     ios_base::sync_with_stdio(0); cin.tie(0);
  70.     int test = 1;
  71.     cin>>test;
  72.     while(test--)
  73.     {
  74.         cin>>n>>k;
  75.         cur_trie = 0;
  76.         for(int i=0; i<=n*30; i+=1) nxt[i][1]=nxt[i][0]=-1, mx[i]=-1;
  77.         for(int i=1; i<=n; i+=1) cin>>a[i];
  78.         solve();
  79.     }
  80. }
Success #stdin #stdout 0.01s 5648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/j1aqIo
6
5 0
1 2 3 4 5
5 7
1 2 3 4 5
5 8
1 2 3 4 5
5 7
3 5 1 4 2
5 3
3 5 1 4 2
6 71
26 56 12 45 60 27
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!