Submission #2440002
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T,Int X>
struct BinaryTrie{
struct Node{
bool f;
T laz;
int par,cnt,nxt[2];
Node(){}
Node(bool f,int par):
f(f),laz(0),par(par),cnt(0){nxt[0]=nxt[1]=-1;}
};
vector<Node> v;
queue<int> q;
BinaryTrie(){v.emplace_back(0,-1);}
void emplace(bool f,int par){
while(!q.empty()&&q.front()<0) q.pop();
if(q.empty()){
v[par].nxt[f]=v.size();
v.emplace_back(f,par);
}else{
v[par].nxt[f]=q.front();
v[q.front()]=Node(f,par);
q.pop();
}
}
inline int count(int x){
return x<0?0:v[x].cnt;
}
inline void eval(int i,int x){
if((v[x].laz>>i)&1){
swap(v[x].nxt[0],v[x].nxt[1]);
v[x].laz^=T(1)<<i;
}
for(int k=0;k<2;k++){
if(!~v[x].nxt[k]) continue;
v[v[x].nxt[k]].laz^=v[x].laz;
v[v[x].nxt[k]].f=k;
}
v[x].laz=0;
}
void add(const T b){
int pos=0;
for(int i=X-1;i>=0;i--){
eval(i,pos);
bool f=(b>>i)&1;
if(v[pos].nxt[f]<0) emplace(f,pos);
pos=v[pos].nxt[f];
}
v[pos].cnt++;
for(int i=0;i<X;i++){
pos=v[pos].par;
v[pos].cnt=count(v[pos].nxt[0])+count(v[pos].nxt[1]);
}
}
void update(const T b){
v[0].laz^=b;
}
int find(const T b){
int pos=0;
for(int i=X-1;i>=0;i--){
eval(i,pos);
bool f=(b>>i)&1;
if(~v[pos].nxt[f]) pos=v[pos].nxt[f];
else return -1;
}
return pos;
}
void erase(int pos){
v[pos].cnt--;
for(int i=0;i<X;i++){
pos=v[pos].par;
v[pos].cnt=count(v[pos].nxt[0])+count(v[pos].nxt[1]);
for(int k=0;k<2;k++){
if(!count(v[pos].nxt[k])){
q.emplace(v[pos].nxt[k]);
v[pos].nxt[k]=-1;
}
}
}
}
int xmax(const T b){
int pos=0;
for(int i=X-1;i>=0;i--){
eval(i,pos);
bool f=(~b>>i)&1;
f^=!~v[pos].nxt[f];
pos=v[pos].nxt[f];
}
return pos;
}
int xmin(const T b){
return xmax(~b&((T(1)<<X)-1));
}
int next(int pos){
for(int i=-1;i<X;i++){
int par=v[pos].par;
if(v[pos].f==0&&~v[par].nxt[1])
return fmin(i,v[par].nxt[1]);
pos=par;
}
while(1);
return pos;
}
int fmin(int i,int pos){
if(i==-1) return pos;
eval(i,pos);
return fmin(i-1,v[pos].nxt[v[pos].nxt[0]==-1]);
}
T val(int pos){
if(pos<0) while(1);
T res=0;
for(int i=0;i<X;i++){
res|=T(v[pos].f)<<i;
pos=v[pos].par;
}
return res;
}
void show(){
vector<T> vs;
T a=val(xmin(0));
vs.emplace_back(a);
int pos=find(a);
while(val(xmax(0))!=a){
pos=next(pos);
a=val(pos);
vs.emplace_back(a);
}
cout<<"#######"<<endl;
for(T x:vs) cout<<x<<" ";
cout<<endl;
}
};
//END CUT HERE
//INSERT ABOVE HERE
signed JAG2013SUMMERWARMINGUP_F(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
vector<int> s(n+1,0);
for(int i=0;i<n;i++) s[i+1]=s[i]^a[i];
map<int, int> r;
BinaryTrie<int, 30> bt;
bt.add(0);
r[bt.find(0)]=0;
int ans=-1,idx=-1,idy=-1;
for(int i=0;i<n;i++){
int k=r[bt.xmax(a[i])];
int res=s[i+1]^s[k];
if(ans<res||(ans==res&&idx>k)){
ans=res;
idx=k;
idy=i;
}
bt.update(a[i]);
bt.add(0);
if(!r.count(bt.find(0))) r[bt.find(0)]=i+1;
}
cout<<ans<<" "<<idx+1<<" "<<idy+1<<endl;
return 0;
}
/*
verified on 2018/04/30
https://beta.atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_f
*/
signed CFR470_C(){
int n;
scanf("%d",&n);
vector<int> a(n),p(n);
for(Int i=0;i<n;i++) scanf("%d",&a[i]);
for(Int i=0;i<n;i++) scanf("%d",&p[i]);
map<int, int> r;
BinaryTrie<int, 30> bt;
for(int i=0;i<n;i++){
bt.add(p[i]);
if(!r.count(bt.find(p[i])))
r[bt.find(p[i])]=i;
}
for(Int i=0;i<n;i++){
if(i) printf(" ");
int k=r[bt.xmin(a[i])];
printf("%d",a[i]^p[k]);
bt.erase(bt.find(p[k]));
}
puts("");
return 0;
}
/*
verified on 2018/04/30
http://codeforces.com/contest/947/problem/C
*/
signed CFR477_C(){
Int n;
scanf("%lld",&n);
vector<Int> b(n);
for(Int i=0;i<n;i++) scanf("%lld",&b[i]);
BinaryTrie<Int, 60> bt;
for(Int i=0;i<n;i++) bt.add(b[i]);
Int z=0;
auto apply=[&](Int a){
z^=a;
bt.update(a);
};
vector<Int> ans;
Int x=bt.val(bt.xmin(0));
ans.emplace_back(x);
bt.erase(bt.find(x));
apply(x);
for(Int i=1;i<n;i++){
bt.add(x);
Int pos=bt.find(x);
if(bt.val(bt.xmax(0))==x){
printf("No\n");
return 0;
}
Int nxt=bt.next(pos);
Int y=bt.val(nxt);
ans.emplace_back(y^z);
bt.erase(pos);
bt.erase(nxt);
apply(x^y);
x=y;
}
printf("Yes\n");
for(Int i=0;i<n;i++){
if(i) printf(" ");
printf("%lld",ans[i]);
}
printf("\n");
return 0;
}
/*
verified on 2018/04/30
http://codeforces.com/contest/966/problem/C
*/
signed main(){
JAG2013SUMMERWARMINGUP_F();
//CFR470_C();
//CFR477_C();
return 0;
}
Submission Info
Submission Time
2018-04-30 20:53:33+0900
Task
F - Maximum Segment XOR
User
beet
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
5346 Byte
Status
AC
Exec Time
200 ms
Memory
18428 KB
Compile Error
./Main.cpp: In function ‘int CFR470_C()’:
./Main.cpp:187:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:189:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(Int i=0;i<n;i++) scanf("%d",&a[i]);
^
./Main.cpp:190:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(Int i=0;i<n;i++) scanf("%d",&p[i]);
^
./Main.cpp: In function ‘int CFR477_C()’:
./Main.cpp:215:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:217:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attrib...
Judge Result
Set Name
All
Score / Max Score
100 / 100
Status
Set Name
Test Cases
All
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 4, 5, 6, 7, 8, 9
Case Name
Status
Exec Time
Memory
1
AC
1 ms
256 KB
10
AC
3 ms
720 KB
11
AC
2 ms
588 KB
12
AC
2 ms
512 KB
13
AC
11 ms
1928 KB
14
AC
14 ms
2056 KB
15
AC
16 ms
3716 KB
16
AC
104 ms
8324 KB
17
AC
57 ms
8960 KB
18
AC
196 ms
16632 KB
19
AC
1 ms
256 KB
2
AC
1 ms
256 KB
20
AC
1 ms
256 KB
21
AC
1 ms
256 KB
22
AC
2 ms
256 KB
23
AC
1 ms
256 KB
24
AC
2 ms
256 KB
25
AC
6 ms
864 KB
26
AC
3 ms
612 KB
27
AC
13 ms
1312 KB
28
AC
134 ms
17404 KB
29
AC
142 ms
15868 KB
3
AC
1 ms
256 KB
30
AC
86 ms
9216 KB
31
AC
200 ms
18428 KB
4
AC
1 ms
256 KB
5
AC
1 ms
256 KB
6
AC
1 ms
256 KB
7
AC
1 ms
384 KB
8
AC
1 ms
256 KB
9
AC
2 ms
592 KB