Submission #522764

#	Time	Username	Problem	Language	Result	Execution time	Memory
522764		Theo830	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	926 ms	28952 KiB

xorsum

#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 = 30;
    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(i);
            }
            else{
                exo[0].pb(i);
            }
        }
        ll neo = 0;
        ll e[n];
        ll e2[n];
        for(auto x:exo[0]){
            e[neo] = pre[x];
            e2[neo] = pos[x];
            neo++;
        }
        for(auto x:exo[1]){
            e[neo] = pre[x] + (1LL<<j);
            e2[neo] = pos[x];
            neo++;
        }
        f(i,0,n){
            pre[i] = e[i];
            pos[i] = e2[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";
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23