/**
(وَأَنْ لَيْسَ لِلْإِنْسَانِ إِلَّا مَا سَعَىٰ * وَأَنَّ سَعْيَهُ سَوْفَ يُرَىٰ)
(النجم: 39-40)
**/
// Always keep moving
//#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef __int128_t Big;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
//#define int long long
#define Fcin ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);
const ll oo = (ll)1e18+1;
#define eb emplace_back
#define pb push_back
#define in insert
#define fs first
#define sc second
const ll MOD=1e9+7;
#define all(ds) ds.begin(),ds.end()
#define rall(ds) ds.rbegin(),ds.rend()
#define Sort(ds) sort(ds.begin(),ds.end())
#define sortc(ds,co) sort(ds.begin(),ds.end(),co)
#define FastFib(n) round((double)(pow((1+sqrt(5)),n)-pow((1-sqrt(5)),n))/(double)((1<<n)*sqrt(5)))
#define popCnt(x) (__builtin_popcountll(x))
#define show(name) Show(#name,(name))
void Show(char *name,ll value)
{
cout<<name<<" = "<<value<<endl;
}
/*
struct SegTree{
#define lf (x * 2 + 1)
#define rt (x * 2 + 2)
#define md ((lx+rx)>>1)
int n;
vector<array<int,2>> tree;
SegTree(int m)
{
n = m+1;
tree.assign(n*4,{0,0});
build(0,n);
}
void build(int l,int r ,int x = 0,int lx = 0,int rx = -1)
{
if(rx==-1)
rx = n-1;
if(lx==rx)
{
tree[x] = {0,rx};
return ;
}
build(l,r,lf,lx,md);
build(l,r,rt,md+1,rx);
tree[x] = merge(tree[lf],tree[rt]);
}
void update(int i,int val,int x = 0,int lx = 0,int rx = -1)
{
if(rx==-1)
rx = n-1;
if(lx==rx){
tree[x][0] += val;
return ;
}
if(i<=md)
update(i,val,lf,lx,md);
else
update(i,val,rt,md+1,rx);
tree[x] = merge(tree[lf] , tree[rt]);
}
array<int,2> query(int l,int r,int x = 0,int lx = 0,int rx = -1)
{
if(rx==-1)
rx = n-1;
if(rx<l or lx>r)return {false,0};
if(lx>=l and rx<=r)return tree[x];
return merge(query(l,r,lf,lx,md) , query(l,r,rt,md+1,rx));
}
#undef lf
#undef rt
#undef md
};
*/
string s;
const int m = 1e9+7;
struct Hash{
int p , n;
vector<int> h,pw;
Hash(int nt,int pt) : n(nt) , p(pt)
{
h.resize(n+1);
pw.resize(n+1);
init();
hash_s();
}
void hash_s()
{
h[0] = 0;
for(int i=1;i<=s.size();i++)
{
h[i] = ((h[i-1]*p)+(s[i-1]-'a'+1))%m;
}
}
int calc(int l,int r)
{
return ((h[r]-h[l-1]*pw[r-l+1])%m + m)%m;
}
void init()
{
pw[0] = 1;
for(int i=1;i<=n;i++)
pw[i] = (pw[i-1]*p)%m;
}
};
struct Hash_sfx{
int p , n ;
vector<int> h,pw;
Hash_sfx(int nt,int pt) : n(nt) , p(pt)
{
h.resize(n+2);
pw.resize(n+2);
init();
hash_s();
}
void hash_s()
{
h.back() = 0;
for(int i=s.size();i>=1;i--)
{
h[i] = ((h[i+1]*p)+(s[i-1]-'a'+1))%m;
}
}
int calc(int l,int r)
{
return ((h[l]-h[r+1]*pw[r-l+1])%m + m)%m;
}
void init()
{
pw[0] = 1;
for(int i=1;i<=n;i++)
pw[i] = (pw[i-1]*p)%m;
}
};
struct node{
int next[2] = {};
int cnt,mn;
node(){cnt = 0;mn = 1e9;}
};
/*
void push(vector<node> &trie,string &s)
{
int cur = 0;
for(int i=0;i<s.size();i++)
{
if(!trie[cur].next.count(s[i]-'a'))
trie[cur].next[s[i]-'a'] = trie.size() ,
trie.emplace_back() , trie[trie.size()-1].ch = s[i];
cur = trie[cur].next[s[i]-'a'];
trie[cur].cnt++;
}
trie[cur].end_cnt++;
}
int check(vector<node> &trie,string &s){
int u = 0;
for(auto c:s)
{
if(!trie[u].next[c-'a'])return false;
u = trie[u].next[c-'a'];
}
return true;
}
int search (vector<node> &trie,string &s,int i,int u){
if(i==s.size() or !trie[u].next.count(s[i]-'a'))return trie[u].cnt;
return (u?trie[u].cnt:0) + search(trie,s,i+1,trie[u].next[s[i]-'a']);
};
*/
signed main()
{
Fcin
ll t,i,a,b,x,m,w,y;
t=1;
// cin>>t;
cout<<fixed<<setprecision(9);
while(t--)
{
int n,q,k;
cin>>n>>k;
vector<int> v(n);
for(auto &n:v)cin>>n;
int cur = 0;
vector<node> trie(1);
auto push = [](vector<node> &trie,int n,int idx)
{
int u = 0;
for(int i=30;i>=0;i--)
{
if(!trie[u].next[n>>i&1])
trie[u].next[n>>i&1] = trie.size() , trie.emplace_back();
u = trie[u].next[n>>i&1];
trie[u].mn = min(trie[u].mn,idx);
trie[u].cnt++;
}
};
auto solve = [](vector<node> &trie,int n,int k)
{
ll u = 0 ;
int res = 1e9 , i = 32;
for(i=30;i>=0;i--)
{
if((n>>i&1) and (k>>i&1))
{
u = trie[u].next[0];
}else if((n>>i&1) and !(k>>i&1))
{
res = min(res,trie[trie[u].next[0]].mn);
u = trie[u].next[1];
}else if(!(n>>i&1) and (k>>i&1))
{
u = trie[u].next[1];
}else {
res = min(res,trie[trie[u].next[1]].mn);
u = trie[u].next[0];
}
if(!u)break;
}
return res;
};
array<int,2> ans = {-1,-1};
for(i=0;i<n;i++)
{
cur ^= v[i];
push(trie,cur,i);
int j = solve(trie,cur,k)+1;
if(i-j>ans[1]-ans[0])ans = {j,i};
}
cout<<ans[0]+1<<" "<<ans[1]-ans[0]+1;
}
}
컴파일 시 표준 에러 (stderr) 메시지
xor.cpp: In function 'int main()':
xor.cpp:335:43: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
335 | if(i-j>ans[1]-ans[0])ans = {j,i};
| ^| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
