Segment Cost
Problem
You are given an array of integers A of size N. Cost of a segment (L,R) is defined as (A[L]+A[L+1]+....+A[R]) - (A[L]⊕A[L+1]⊕....⊕A[R]) (where ⊕ denotes the Bitwise XOR operator).
Given a range (x,y), find the smallest subsegment (x′,y′) such that x≤x′≤y′≤y and its cost is maximum among all the subsegments of (x,y).
If there exists more than answer, print the subsegment with smallest x′.
Input format
- First line contains an integer N
- Second line contains N space-separated integers denoting the array A
- Next line contains two space separated integer x y
Output format
Print two space separated integers x′ y′ denoting the subsegment.
Constraints
1≤N≤1050≤A[i]≤1091≤x≤y≤N
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
- Cost of A[1,1]=5−5=0
- Cost of A[2,2]=10−10=0
- Cost of A[1,2]=(10+5)−(10⊕5)=0
Since, we have more than one answer, we will return the answer where
- Segment has a minimum length
- x′ is minimum.
Thus, required answer is (1,1)
