#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin>>n;
ll arr[n];
ll pos[n];
f(i,0,n){
cin>>arr[i];
pos[i] = i;
}
const ll m = 29;
ll ans = 0;
ll pre[n] = {0};
f(j,0,m){
///[2^j,2^(j+1) - 1]
///[2^(j+1) + 2^j,2^(j+2) - 1]
vector<ll> exo[2];
f(i,0,n){
if(arr[pos[i]] & (1LL<<j)){
exo[1].pb(pos[i]);
}
else{
exo[0].pb(pos[i]);
}
}
ll neo = 0;
ll e[n];
for(auto x:exo[0]){
e[neo] = pre[pos[x]];
pos[x] = neo;
neo++;
}
for(auto x:exo[1]){
e[neo] = pre[pos[x]] + (1LL<<j);
pos[x] = neo;
neo++;
}
f(i,0,n){
pre[i] = e[i];
}
ll L1 = (1LL<<j),R1 = (1LL<<(j+1)) - 1;
ll L2 = (1LL<<j) + (1LL<<(j+1));
ll l1,r1,l2,r2;
l1 = l2 = r1 = r2 = n - 1;
//cout<<j<<": \n";
//cout<<L1<<" "<<R1<<" "<<L2<<" "<<R2<<"\n";
bool ok = 0;
f(i,0,n){
while(l1 > 0 && pre[l1 - 1] + pre[i] >= L1){
l1--;
}
while(l2 > 0 && pre[l2 - 1] + pre[i] >= L2){
l2--;
}
while(r1 >= 0 && pre[r1] + pre[i] > R1){
r1--;
}
ll y = l1;
l1 = max(l1,i);
ll y2 = l2;
l2 = max(l2,i);
//cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
if(r1 >= l1 && pre[i] + pre[l1] >= L1){
//cout<<"ev1\n";
ok ^= (r1 - l1 + 1) % 2;
}
if(r2 >= l2 && pre[i] + pre[l2] >= L2){
//cout<<"ev2\n";
ok ^= (r2 - l2 + 1) % 2;
}
l1 = y;
l2 = y2;
}
ans += ok * (1LL<<j);
}
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
760 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
760 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
