Dear All,

I have solved the problem using dynamic programming where dp[i][0] indicates not to include the current element i into the set and dp[i][1] indicates to include the current element into the set. Here is my code:

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

long long int a[100001];

long long int dp[100002][2];

int main()
{
    long int n,i;
    scanf("%ld",&n);
    for ( i = 1 ; i <= n ; i++ ){
        scanf("%lld",&a[i]);
    }
    //memset(dp, 0, sizeof(dp[0][0]) * 2 * 100002);
    for( i = n ; i >= 1 ; i--){
        dp[i][0] = max(dp[i+1][0] ^ 0 , dp[i+1][1] ^ 0);
        dp[i][1] = max(dp[i+1][0] ^ a[i],dp[i+1][1] ^ a[i]);
    }
    dp[0][0] = max(dp[1][0]^0,dp[1][1]^0);
    printf("%lld",dp[0][0]);
}

I am getting a wrong answer even though the test cases I tried are giving the correct ouput. I checked the constraints as well and the data types are correct. It is a very short code. Could someone please help me?

Thank you.

Dear all,

here is the link for the problem. My solution involved using segment tree. I have read the editorial and understood the basic idea. But in the editorial it is written that we cannot use segement tree as it will result in TLE. I am unable to understand the trick(not using segment tree) that is mentioned in the editorial which runs in linear time to store the GCD of the subarrays. Could someone help me with understanding the solution of the editorial? If you have any other solution please let me know.

Thank you.