Balanced Boxing Segments
Национална олимпиада - Национален кръг 2025
Submission name: boxing.cpp
Problem summary
Generate a nonnegative strength sequence. Count its nonempty contiguous segments that can be split into a left and right part, each with total strength at least K. Count a segment once, even if several splits work. Empty sides are permitted when K=0.
Input
N K, then a1 a2 X Y Z M. For i ≥ 3, ai=(a[i−2]X+a[i−1]Y+Z) mod M.
Output
The number of qualifying segments.
Constraints
1 ≤ N ≤ 10^7; 0 ≤ K ≤ 10^16; 0 ≤ a1,a2 < M; X,Y,Z ≤ M ≤ 2×10^9. Both seeds are supplied even for N=1.
Worked example
The worked example illustrates the rule described in the analysis.
Input
5 10 10 6 12 15 13 15
Output
7
Solution analysis
- Generate strengths in a 32-bit unsigned vector, but evaluate each recurrence in 64-bit arithmetic. For K=0, all N(N+1)/2 nonempty segments qualify.
- For a fixed left endpoint, choose the earliest middle for which the left sum reaches K. Nonnegative values mean every later split leaves no more strength for the right side, so this earliest middle is optimal.
- Extend an exclusive end pointer until the right part also reaches K. Every ending position from end−1 onward qualifies, contributing N−end+1. Advance the left endpoint and subtract its strength from the left sum.
- When the middle moves through the existing right part, transfer that value from rightSum to leftSum. All three pointers move only forward. The sample generates 10,6,13,10,4 and has seven qualifying segments.
Why it works
For each left endpoint the earliest feasible split maximizes the available suffix. The earliest feasible ending for that split is consequently the earliest ending for any split. Nonnegative strengths make all longer segments valid and permit monotone pointers. Each segment is counted once by its unique left endpoint.
Watch out. Count segments rather than valid splits. Handle K=0 separately, preserve zero strengths, and avoid 32-bit recurrence multiplication. Do not read a2 conditionally on N.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
int n;
long long threshold,first,second,x,y,z,modulo;
cin>>n>>threshold;
cin>>first>>second>>x>>y>>z>>modulo;
if(threshold==0){
cout<<1LL*n*(n+1)/2<<'\n';
return 0;
}
vector<uint32_t>strength(n);
strength[0]=static_cast<uint32_t>(first);
if(n>1){
strength[1]=static_cast<uint32_t>(second);
}
for(int i=2;i<n;++i){
strength[i]=static_cast<uint32_t>((strength[i-2]*x+strength[i-1]*y+z)%modulo);
}
int middle=0,end=0;
long long leftSum=0,rightSum=0,answer=0;
for(int left=0;left<n;++left){
while(middle<n&&leftSum<threshold){
leftSum+=strength[middle];
// Transfer an already included value out of the right part.
if(middle<end){
rightSum-=strength[middle];
}
else{
end=middle+1;
}
++middle;
}
while(end<n&&rightSum<threshold){
rightSum+=strength[end];
++end;
}
if(leftSum<threshold||rightSum<threshold){
break;
}
answer+=n-end+1;
leftSum-=strength[left];
}
cout<<answer<<'\n';
}