Submission #3461282
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T,size_t X>
struct BinaryTrie{
struct Node{
bool f;
size_t cnt;
Node *p,*l,*r;
Node(bool f,Node* p):f(f),cnt(0),p(p){l=r=nullptr;}
};
T acc;
Node *root;
BinaryTrie():acc(0){root=emplace(0,nullptr);}
inline Node* emplace(bool f,Node* p){
return new Node(f,p);
}
inline size_t count(Node* a){
return a?a->cnt:0;
}
void add(const T b,size_t k=1){
const T nb=b^acc;
Node* a=root;
for(int i=X-1;i>=0;i--){
bool f=(nb>>i)&1;
if(!f&&!a->l) a->l=emplace(f,a);
if( f&&!a->r) a->r=emplace(f,a);
a=f?a->r:a->l;
}
a->cnt+=k;
while((a=a->p)) a->cnt=count(a->l)+count(a->r);
}
inline void update(const T b){acc^=b;}
Node* find(const T b){
const T nb=b^acc;
Node* a=root;
for(int i=X-1;i>=0;i--){
bool f=(nb>>i)&1;
a=f?a->r:a->l;
if(!a) return a;
}
return a;
}
Node* check(Node *a){
if(!a||count(a)) return a;
delete(a);
return nullptr;
}
void sub(Node* a,size_t k=1){
assert(a&&a->cnt>=k);
a->cnt-=k;
while((a=a->p)){
a->l=check(a->l);
a->r=check(a->r);
a->cnt=count(a->l)+count(a->r);
}
}
Node* xmax(const T b){
assert(count(root));
const T nb=b^acc;
Node* a=root;
for(int i=X-1;i>=0;i--){
bool f=(nb>>i)&1;
a=(!a->l||(!f&&a->r))?a->r:a->l;
}
return a;
}
int xmin(const T b){
return xmax(~b&((T(1)<<X)-1));
}
Node* ge(Node *a){
if(a&&(a->r||a->l)) return a->l?a->l:a->r;
return a;
}
Node* next(Node* a){
while(a->p){
if(a->p->l==a) return ge(a->p->r);
a=a->p;
}
return nullptr;
}
Node* lower_bound(const T b){
const T nb=b^acc;
Node* a=root;
for(int i=X-1;i>=0;i--){
bool f=(nb>>i)&1;
if(!f&&a->l){a=a->l;continue;}
if( f&&a->r){a=a->r;continue;}
if(f) return next(a);
return ge(a->r);
}
return a;
}
int upper_bound(const T b){
return lower_bound(b+1);
}
T val(Node* a){
T res(0);
for(int i=0;i<(int)X;i++){
bool f=(acc>>i)&1;
res|=(T(a->f)<<i)^f;
a=a->p;
}
return res^acc;
}
Node* find_by_order(size_t k){
Node *a=root;
if(count(a)<=k) return nullptr;
for(int i=X-1;i>=0;i--){
bool f=(acc>>i)&1;
if(count(f?a->r:a->l)<=k){
k-=count(f?a->r:a->l);
a=f?a->l:a->r;
}else{
a=f?a->r:a->l;
}
}
return a;
}
size_t order_of_key(const T b){
const T nb=b^acc;
Node *a=root;
size_t res;
for(int i=X-1;i>=0;i--){
bool f=(nb>>i)&1;
if(f) res+=count(a->l);
a=f?a->r:a->l;
if(!a) break;
}
return res;
}
};
//END CUT HERE
signed JAG2013SUMMERWARMINGUP_F(){
int n;
scanf("%d",&n);
vector<int> a(n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
vector<int> s(n+1,0);
for(int i=0;i<n;i++) s[i+1]=s[i]^a[i];
BinaryTrie<int, 30> bt;
using ull = unsigned long long;
map<ull, int> r;
bt.add(0);
r[(ull)bt.find(0)]=0;
int ans=-1,idx=-1,idy=-1;
for(int i=0;i<n;i++){
int k=r[(ull)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((ull)bt.find(0))) r[(ull)bt.find(0)]=i+1;
}
printf("%d %d %d\n",ans,idx+1,idy+1);
return 0;
}
/*
verified on 2018/10/24
https://beta.atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_f
*/
signed ARC033_C(){
int q;
scanf("%d",&q);
BinaryTrie<int, 30> bt;
while(q--){
int t,x;
scanf("%d %d",&t,&x);
if(t==1) bt.add(x);
if(t==2){
//printf("t: %d, x: %d\n",t,x);
auto k=bt.find_by_order(x-1);
//printf("t: %d, x: %d\n",t,x);
printf("%d\n",bt.val(k));
bt.sub(k);
}
}
return 0;
}
/*
verified on 2018/10/24
https://beta.atcoder.jp/contests/arc033/tasks/arc033_3
*/
signed main(){
JAG2013SUMMERWARMINGUP_F();
//ARC033_C();
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Maximum Segment XOR |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4355 Byte |
Status |
AC |
Exec Time |
153 ms |
Memory |
28288 KB |
Compile Error
./Main.cpp: In function ‘int JAG2013SUMMERWARMINGUP_F()’:
./Main.cpp:154:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:156: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: In function ‘int ARC033_C()’:
./Main.cpp:187:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:191:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&t,&x);
^
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 |
2 ms |
768 KB |
11 |
AC |
2 ms |
640 KB |
12 |
AC |
1 ms |
512 KB |
13 |
AC |
9 ms |
2944 KB |
14 |
AC |
11 ms |
3456 KB |
15 |
AC |
13 ms |
4096 KB |
16 |
AC |
77 ms |
13056 KB |
17 |
AC |
45 ms |
11392 KB |
18 |
AC |
153 ms |
28288 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 |
1 ms |
256 KB |
23 |
AC |
1 ms |
256 KB |
24 |
AC |
1 ms |
256 KB |
25 |
AC |
4 ms |
1024 KB |
26 |
AC |
2 ms |
640 KB |
27 |
AC |
8 ms |
1536 KB |
28 |
AC |
98 ms |
17792 KB |
29 |
AC |
109 ms |
19200 KB |
3 |
AC |
1 ms |
256 KB |
30 |
AC |
64 ms |
12800 KB |
31 |
AC |
143 ms |
21376 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 |
640 KB |