Split Intervals by Full OR and Zero AND
Autumn Tournament (2025)
Submission name: oriand.cpp
Problem summary
Count intervals of at least two elements that admit a split into a left part with bitwise OR equal to2^K−1 and a right part with bitwise AND equal to0. Count an interval only once even when several splits work.
Source clarification. The Group B version uses a grader function and N≤1000000, unlike the smaller standalone Group C version. This implementation uses a linear aggregate queue rather than O(NK) bit scans.
Input
Official interface: long long oriand(int N,int K,vector<long long>A). The LOCAL driver reads N K and N values.
Output
Return the number of valid intervals; the LOCAL driver prints it.
Constraints
1≤N≤1000000;1≤K≤63;0≤A[i]≤2^K−1.
Worked example
Original statement sample.
Input
6 1 1 0 0 0 1 0
Output
9
Solution analysis
- For every left endpointL, find the earliest endpointE[L] where the prefix OR becomes the all-ones mask. If a valid split exists, choosing this earliest prefix is never worse: its right part begins earlier, and adding elements to an AND can only clear bits. Therefore the earliest possible right endpoint is Z[E[L]+1], whereZ[S] is the earliest endpoint giving AND0 fromS.
- Compute earliest full-OR endpoints with a sliding window. Its aggregate is maintained by a queue made from two stacks, each storing prefix ORs. Push the right endpoint until the aggregate is full, record it, then pop the left endpoint. When the output stack is empty, transfer the input stack in reverse; each value is moved only once. This gives O(1) amortized aggregate operations without looping overK bits.
- An AND is zero exactly when the OR of the K-bit complements is full. Run the same procedure on A[i] XOR fullMask to obtainZ. If E[L]+1<N and the resultingZ isR, all N−R choices of right endpoint work. In the sample, L=0 permits five ends; L=1,2,3,4 each permit only end5, giving9.
Why it works
OR-fullness is monotone as the right endpoint grows, so two pointers find the exact earliest prefix. Among valid prefixes the earliest leaves the largest suffix; its AND-zero endpoint cannot be later than that of a suffix starting later. Thus an interval is valid iff its right endpoint is at least Z[E[L]+1]. The two-stack OR is exactly the OR of every queue element, and complementation correctly exchanges AND-zero with OR-full.
Watch out. Use an unsigned64-bit mask:1ULL<<K is valid forK=63. Restrict complements toK bits. Reject a prefix that already uses the last array element, because both parts must be nonempty. Do not count one interval once per possible split.
Commented C++17 solution
This is a function-graded problem. Submit the oriand function and its helper, without the LOCAL main. To run the displayed input/output example independently, compile with g++ -std=c++17 -DLOCAL. The official signature is preserved.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
using Bits=unsigned long long;
vector<int>earliestFull(const vector<long long>&values,Bits full,bool complement){
int n=static_cast<int>(values.size());
vector<pair<Bits,Bits>>input,output;
vector<int>endpoint(n,n);
int right=0;
auto aggregate=[&](){
Bits a=input.empty()?0:input.back().second;
Bits b=output.empty()?0:output.back().second;
return a|b;
};
for(int left=0;left<n;left++){
while(right<n&&aggregate()!=full){
Bits value=static_cast<Bits>(values[right]);
if(complement){
value^=full;
}
Bits combined=value|(input.empty()?0:input.back().second);
input.push_back({value,combined});
right++;
}
if(aggregate()==full){
endpoint[left]=right-1;
}
if(output.empty()){
// Reverse the input stack so that the oldest value is on top.
while(!input.empty()){
Bits value=input.back().first;
input.pop_back();
Bits combined=value|(output.empty()?0:output.back().second);
output.push_back({value,combined});
}
}
if(!output.empty()){
output.pop_back();
}
}
return endpoint;
}
long long oriand(int N,int K,vector<long long>A){
Bits full=(1ULL<<K)-1;
vector<int>prefixEnd=earliestFull(A,full,false);
vector<int>suffixEnd=earliestFull(A,full,true);
long long answer=0;
for(int left=0;left<N;left++){
int start=prefixEnd[left]+1;
if(start<N){
answer+=N-suffixEnd[start];
}
}
return answer;
}
#ifdef LOCAL
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin>>n>>k;
vector<long long>values(n);
for(long long&value:values){
cin>>value;
}
cout<<oriand(n,k,values)<<'\n';
}
#endif