Submission #2438411
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;}
};
const int lim=7e6;
int idx;
vector<Node> v;
BinaryTrie():idx(0),v(lim){emplace(0,-1);}
void emplace(bool f,int par){
v[idx++]=Node(f,par);
}
void rebuild(){
vector<T> vs;
vector<int> vc;
T a=val(xmin(0));
int pos=find(a);
vs.emplace_back(a);
vc.emplace_back(v[pos].cnt);
while(val(xmax(0))!=a){
pos=next(pos);
a=val(pos);
vs.emplace_back(a);
vc.emplace_back(v[pos].cnt);
}
idx=0;
emplace(0,-1);
for(int i=0;i<(int)vs.size();i++)
for(int j=0;j<vc[i];j++) add(vs[i]);
}
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]){
pos=v[pos].nxt[f];
continue;
}
int npos=idx;
v[pos].nxt[f]=npos;
emplace(f,pos);
pos=npos;
}
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){
if(pos<0) while(1);
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])) 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);
r[bt.find(0)]=i+1;
}
cout<<ans<<" "<<idx+1<<" "<<idy+1<<endl;
return 0;
}
/*
verified on 2018/03/11
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]);
BinaryTrie<int, 30> bt;
for(int i=0;i<n;i++) bt.add(p[i]);
for(Int i=0;i<n;i++){
if(i) printf(" ");
int k=bt.xmin(a[i]);
printf("%d",a[i]^p[k]);
bt.erase(bt.find(p[k]));
}
puts("");
return 0;
}
/*
verified on 2018/03/11
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;
if(bt.idx+1000>=bt.lim) bt.rebuild();
}
printf("Yes\n");
for(Int i=0;i<n;i++){
if(i) printf(" ");
printf("%lld",ans[i]);
}
printf("\n");
return 0;
}
signed main(){
JAG2013SUMMERWARMINGUP_F();
//CFR470_C();
return 0;
}
Submission Info
Submission Time
2018-04-30 14:42:30+0900
Task
F - Maximum Segment XOR
User
beet
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
5504 Byte
Status
WA
Exec Time
174 ms
Memory
16512 KB
Compile Error
./Main.cpp: In function ‘int CFR470_C()’:
./Main.cpp:204:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:206: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:207: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:228:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:230:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attrib...
Judge Result
Set Name
All
Score / Max Score
0 / 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
2 ms
512 KB
11
AC
2 ms
384 KB
12
AC
2 ms
384 KB
13
AC
10 ms
3328 KB
14
AC
12 ms
2048 KB
15
AC
14 ms
4096 KB
16
AC
90 ms
8832 KB
17
AC
48 ms
7040 KB
18
WA
170 ms
16512 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
640 KB
26
AC
3 ms
512 KB
27
AC
12 ms
1024 KB
28
AC
114 ms
11136 KB
29
AC
126 ms
12928 KB
3
AC
1 ms
256 KB
30
AC
74 ms
7424 KB
31
AC
174 ms
14592 KB
4
AC
1 ms
256 KB
5
AC
1 ms
256 KB
6
AC
1 ms
256 KB
7
AC
1 ms
256 KB
8
AC
1 ms
256 KB
9
AC
2 ms
384 KB