First register for the contest here.
Idea: injxshn
Using brute force for each query would have a time complexity of $$$O(n)$$$ and hence would exceed the time limit. Since bitwise OR is an increasing function, we then think of binary search.
Given the index $$$k$$$, using binary search, we could find the minimum index $$$r$$$ $$$(k<=r<=n-1)$$$ such that the bitwise OR of elements in the range $$$[k, r]$$$ is the maximum possible bitwise OR obtainable considering the range $$$[k, n-1]$$$. This would give us the right end index $$$r$$$ of required subarray. We could follow a similar approach for the left index $$$l$$$ $$$(0<=l<=k)$$$where we find the maximum index $$$l$$$ such that the bitwise OR of the elements in the range $$$[l, r]$$$ is the maximum possible bitwise OR of the array. We should also consider the case where we find the left end index first and accordingly find the right end index, then we take the minimum of the two lengths of the the subarrays.
To perform binary search, we would need to find the bitwise OR of elements between any two indices in the order of $$$O(1)$$$. We could do this using dynamic programming. We create a 2D array of maximum dimensions $$$n * 32$$$ where $$$dp[i][j]$$$ stores the number of set bits of the element $$$a_i$$$ till the $$$j$$$-th bit. Given two indices $$$l$$$ and $$$r$$$, we could iterate over $$$dp[l]$$$ and $$$dp[r]$$$ to find if a bit is set between the given range. This way we could find the bitwise OR between two indices with a time complexity of $$$O(32)$$$.
The overall time complexity for each query then boils down to $$$O(32 * log(n))$$$ which should pass all the test cases.
#include <bits/stdc++.h>
using namespace std;
// Function to check if the kth bit is set in the number n.
bool isKthBitSet(int n, int k){
if (n & (1 << k))
return true;
else
return false;
}
// Function to calculate the OR between indices using the dp vector.
int or_bw_indices(vector<int>& v, vector<vector<int>>& dp, int l, int r){
int ans = 0;
for (int j = 0; j<32; j++){
if ((l == 0? dp[r][j]: dp[r][j] - dp[l-1][j]) > 0) ans += 1<<j;
}
return ans;
}
void test_case(){
int n,q;
cin >> n >> q;
vector<int> v(n);
for (int i = 0; i<n; i++) cin >> v[i];
// Creaating the dp vector where dp[i][j] stores the number
// of set bits of the ith element till the jth bit.
vector<vector<int>> dp(n, vector<int>(32, 0));
for (int i = 0; i<n; i++){
for (int j = 0; j<32; j++){
if (isKthBitSet(v[i], j)) {
dp[i][j] = (i == 0? 1: dp[i-1][j] + 1);
}
else dp[i][j] = (i == 0? 0: dp[i-1][j]);
}
}
while (q--){
int ind;
cin >> ind;
// Case 1.
// Considering the right side first
int l = ind;
int r = n-1;
int right_max_or = or_bw_indices(v,dp,ind,n-1);
int i = n-1;
while (l<=r){
int mid = l + (r - l)/2;
if (or_bw_indices(v,dp,ind,mid) == right_max_or){
i = min(i, mid);
r = mid-1;
}
else l = mid + 1;
}
// Then the left end.
int left_and_right_max_or = or_bw_indices(v,dp,0,n-1);
l = 0;
r = ind;
int j = 0;
while (l<=r){
int mid = l + (r-l)/2;
if ( (or_bw_indices(v,dp,mid,ind) | right_max_or) == left_and_right_max_or){
j = max(j, mid);
l = mid + 1;
}
else r = mid - 1;
}
// Case2
// Considering the left end first.
int left_max_or = or_bw_indices(v,dp,0,ind);
l = 0;
r = ind;
int i2 = 0;
while (l<=r){
int mid = l + (r-l)/2;
if ((or_bw_indices(v,dp,mid,ind)) == left_max_or){
i2 = max(i2, mid);
l = mid + 1;
}
else r = mid - 1;
}
// Then the right end.
l = ind;
r = n-1;
int j2 = n-1;
while (l<=r){
int mid = l + (r-l)/2;
if ((or_bw_indices(v,dp,ind,mid) | left_max_or) == left_and_right_max_or){
j2 = min(j2, mid);
r = mid-1;
}
else l = mid+1;
}
// Taking the minimum of the sizes of the two sub-arrays formed.
cout << min(j2-i2+1, i-j+1) << endl;
}
}
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
int t=1;
while (t--) test_case();
return 0;
}
Auto comment: topic has been updated by injxshn (previous revision, new revision, compare).
Would you mind checking your problem statement? Here you wrote q is in third line, but in sample test case q is in 1st line. Also, can you assure that 3rd TC is correct?