pypcdev

Untitled

Sep 15th, 2021
551
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //                         _
  2. //   _ __ ___    __ _   __| |  ___
  3. //  | '_ ` _ \  / _` | / _` | / _ \
  4. //  | | | | | || (_| || (_| ||  __/
  5. //  |_| |_| |_| \__,_| \__,_| \___|
  6. //
  7. //   _
  8. //  | |__   _   _
  9. //  | '_ \ | | | |
  10. //  | |_) || |_| |
  11. //  |_.__/  \__, |
  12. //          |___/
  13. //                                  _
  14. //   _ __   _   _  _ __    ___   __| |  ___ __   __
  15. //  | '_ \ | | | || '_ \  / __| / _` | / _ \\ \ / /
  16. //  | |_) || |_| || |_) || (__ | (_| ||  __/ \ V /
  17. //  | .__/  \__, || .__/  \___| \__,_| \___|  \_/
  18. //  |_|     |___/ |_|
  19.  
  20. // -- secret weapon against TL
  21. /*
  22.  
  23. #undef _GLIBCXX_DEBUG
  24. //#pragma GCC optimize("O3")
  25. #pragma GCC optimize("Ofast")
  26. #pragma GCC optimize("inline")
  27. #pragma GCC optimize("-march=native")
  28. #pragma GCC optimize("-mtune=native")
  29. #pragma GCC optimize("-fgcse-lm")
  30. #pragma GCC optimize("-fipa-sra")
  31. #pragma GCC optimize("-ftree-pre")
  32. #pragma GCC optimize("-ftree-vrp")
  33. #pragma GCC optimize("-fpeephole2")
  34. #pragma GCC optimize("-ffast-math")
  35. #pragma GCC optimize("-fsched-spec")
  36. #pragma GCC optimize("-fgcse")
  37. #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                     // bit manipulation
  38. #pragma GCC target("movbe")                                     // byte swap
  39. #pragma GCC target("aes,pclmul,rdrnd")                          // encryption
  40. #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")  // SIMD
  41. #pragma GCC target("tune=native")
  42. #pragma GCC target("avx,avx2,fma")
  43. //#pragma GCC optimization("unroll-loops")
  44. #pragma GCC optimization("funroll-loops")
  45. #pragma GCC optimization("-ftree-vectorize")
  46.  
  47. */
  48.  
  49.  
  50. // https://www.codingame.com/playgrounds/58302/using-pragma-for-compile-optimization
  51.  
  52.  
  53. #include<bits/stdc++.h>
  54. #include<ext/pb_ds/assoc_container.hpp>
  55. #include<ext/pb_ds/tree_policy.hpp>
  56. using namespace std;
  57. using namespace __gnu_pbds;
  58. typedef long long ll;
  59. typedef unsigned long long ull;
  60. typedef long double ld;
  61. #define fi first
  62. #define se second
  63. #define pb push_back
  64. #define pf push_front
  65. #define ppb pop_back
  66. #define ppf pop_front
  67. #define mkp make_pair
  68. mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
  69. mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
  70. #define rand32 rng32
  71. #define rand64 rng64
  72. template<typename type,typename comp>
  73. using ordered_set=tree<type,null_type,comp,rb_tree_tag,tree_order_statistics_node_update>;// advanced set with order_of_key and find_by_order
  74. // aset<int,less<int>> is set, but aset<int,less_equal<int> is multiset
  75. const pair<int,int>DIR4[4]={{1,0},{-1,0},{0,1},{0,-1}}; // dirs for 4 ways(like in a matrix)
  76. const pair<int,int>DIR8[8]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; // dirs for 8 ways(like in a matrix)
  77. bool validf(int up,int left,int down,int right,int i,int ii){
  78.     return up<=i&&i<=down&&left<=ii&&ii<=right;
  79. }
  80.  
  81. int sqrt32(ll x){
  82.     int L=sqrtl(x);
  83.     while(L*L<x)L++;
  84.     while(L*L>x)L--;
  85.     return L;
  86. }
  87. ll sqrt64(ll x){
  88.     ll L=sqrtl(x);
  89.     while(L*L<x)L++;
  90.     while(L*L>x)L--;
  91.     return L;
  92. }
  93.  
  94. ll pow64(ll base,ll exp,ll mod){
  95.     ll res=1;
  96.     while(exp>0){
  97.         if(exp&1)res=res*base,res%=mod;
  98.         exp>>=1;
  99.         base=base*base,base%=mod;
  100.     }
  101.     return res;
  102. }
  103.  
  104. ll div64(ll a,ll b,ll mod){
  105.     return (a%mod)*pow64(b,mod-2,mod)%mod;
  106. }
  107.  
  108. // debug tools only
  109. template<typename F,typename S>ostream&operator<<(ostream&output,const pair<F,S>&data){output<<"{"<<data.fi<<","<<data.se<<"}";return output;}
  110. template<typename T>ostream&operator<<(ostream&output,const set<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  111. template<typename T>ostream&operator<<(ostream&output,const ordered_set<T,less<T>>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  112. template<typename T>ostream&operator<<(ostream&output,const ordered_set<T,greater<T>>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  113. template<typename T>ostream&operator<<(ostream&output,const multiset<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  114. template<typename T>ostream&operator<<(ostream&output,const vector<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  115.  
  116.  
  117.  
  118. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  119. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  120. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  121. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  122. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  123. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  124. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  125. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  126. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  127. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  128. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  129. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  130. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  131. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  132. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  133. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  134. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  135. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  136. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  137. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  138. #define int ll
  139. ifstream in("maxxor.in");
  140. ofstream out("maxxor.out");
  141. #define cin in
  142. #define cout out
  143.  
  144. struct node{
  145.     node*son[2]={};
  146. };
  147. typedef node*pnode;
  148. struct bor{
  149.     pnode root=new node;
  150.     void add(int n){
  151.         pnode v=root;
  152.         for(int k=30;k>=0;k--){
  153.             int bit=(n>>k)&1;
  154.             if(!(v->son[bit]))v->son[bit]=new node;
  155.             v=v->son[bit];
  156.         }
  157.     }
  158.     int get(int n){
  159.         int res=0;
  160.         pnode v=root;
  161.         for(int k=30;k>=0;k--){
  162.             int bit=(n>>k)&1;
  163.             if(v->son[!bit]){
  164.                 res|=((!bit)<<k);
  165.                 v=v->son[!bit];
  166.             }else if(v->son[bit]){
  167.                 res|=(bit<<k);
  168.                 v=v->son[bit];
  169.             }else return -1e9;
  170.         }
  171.         return res;
  172.     }
  173.  
  174.     void clear(pnode v){
  175.         if(v->son[0])clear(v->son[0]);
  176.         if(v->son[1])clear(v->son[1]);
  177.         delete v;
  178.     }
  179.  
  180. };
  181.  
  182.  
  183. const int NMAX=1e5;
  184. int a[NMAX+5];
  185. int pref_xor[NMAX+5],pref_max[NMAX+5];
  186.  
  187. ll getAns(int l,int r){
  188.     if(l==r){
  189.         //cout<<pair{l,r}<<" "<<a[l]*a[l]<<"\n";
  190.         return a[l]*a[l];
  191.     }
  192.     int m=(l+r)/2;
  193.     ll ans=0;
  194.     ans=max(ans,max(getAns(l,m),getAns(m+1,r)));
  195.     pref_xor[m]=pref_max[m]=a[m];
  196.     for(int i=m-1;i>=l;i--)pref_xor[i]=pref_xor[i+1]^a[i],pref_max[i]=max(a[i],pref_max[i+1]);
  197.     pref_xor[m+1]=pref_max[m+1]=a[m+1];
  198.     for(int i=m+2;i<=r;i++)pref_xor[i]=pref_xor[i-1]^a[i],pref_max[i]=max(pref_max[i-1],a[i]);
  199.     bor right;
  200.     int L=m;int R=m+1;
  201.     for(;L>=l;L--){
  202.         while(R<=r&&pref_max[L]>=pref_max[R])right.add(pref_xor[R]),R++;
  203.         ans=max(ans,1ll*pref_max[L]*(pref_xor[L]^right.get(pref_xor[L])));
  204.         //cout<<pair{L,R}<<" "<<pref_max[L]<<" "<<pref_xor[L]<<" "<<right.get(pref_xor[L])<<"\n";
  205.     }
  206.     right.clear(right.root);
  207.     bor left;
  208.     L=m;R=m+1;
  209.     for(;R<=r;R++){
  210.         while(L>=l&&pref_max[R]>=pref_max[L])left.add(pref_xor[L]),L--;
  211.         ans=max(ans,1ll*pref_max[R]*(pref_xor[R]^left.get(pref_xor[R])));
  212.     }
  213.     left.clear(left.root);
  214.     //cout<<pair{l,r}<<" "<<ans<<"\n";
  215.     return ans;
  216. }
  217.  
  218. signed main(){
  219.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  220.     int n;
  221.     cin>>n;
  222.     for(int i=1;i<=n;i++)cin>>a[i];
  223.     cout<<getAns(1,n)<<"\n";
  224. }
  225.  
  226.  
  227.  
RAW Paste Data