Real problems.
Your next challenge.

Problem summary

A planter is the interval[0,L]. Raindrops arrive at pseudorandom integer coordinates. Find the earliest drop after which every gap between consecutive drop positions, including the two ends, is at most D. Return−1 if this never happens.

Source clarification. The output paragraph says a remaining gap “greater than or equal to D” fails, but the main definition, official editorial, and the1-drop L=6,D=3 sample establish that equality succeeds. This solution consistently uses maximum gap≤D. Official O(N) bucket approach: https://infos.infosbg.com/files/Contests/ETI/2015/C/analyses/agrain_analysis.pdf.

Constraints

1 ≤ N ≤ 10000000; 1 ≤ D < L ≤ 1000000000; 0 ≤ X1,A,B ≤ L.

Worked example

Original statement sample.

12 23 7
14 13 5

9

Solution analysis

1. Split coordinates into buckets indexed floor(x/D). Inside one bucket, any two integer coordinates differ by less than D, so only the gaps between neighboring nonempty buckets can prevent success. Keep each bucket’s minimum and maximum encountered coordinates. Pretend positions0 and L are present from the start because they are interval boundaries.
2. For every adjacent bucket pair, record whether its left maximum and right minimum are at distance at most D. A newly arrived drop can change only the two boundaries touching its bucket. Once a boundary connects it never disconnects, so count unconnected boundaries rather than using a linked list or DSU.
3. Let q=floor(L/D), so there are q+1 buckets and q boundaries. If q>N+1, even N drops cannot cut the length into sufficiently short gaps, and the answer is immediately−1. Otherwise bucket storage is O(N). For the sample, the ninth drop is at6; it removes the final gap longer than7 and the boundary counter first reaches zero.
4. The generator multiplication uses long long: multiplying two values up to10^9 exceeds32-bit range. Duplicate drops and drops at either endpoint do not cause duplicate connections because every boundary has its own boolean flag.

Why it works

Within a bucket there is no gap longer than D. Between two occupied neighboring buckets the only relevant gap is rightMinimum−leftMaximum. An empty interior bucket necessarily leaves a gap greater than D, so all q boundaries are connected exactly when the planter is watered. A drop only decreases such gaps, allowing each connection to be counted once. Checking the counter after each generated drop returns the earliest success.

Watch out. Equality with D counts as watered. Include both interval endpoints, but do not count them as real arriving drops. Keep one flag per boundary to avoid decrementing repeatedly. Use64-bit generator arithmetic and reject impossible huge bucket counts before allocating.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int length;
    int limit;
    long long position;
    long long multiplier;
    long long increment;
    cin>>n>>length>>limit;
    cin>>position>>multiplier>>increment;
    int boundaries=length/limit;
    if(boundaries>n+1){
        cout<<-1<<'\n';
        return 0;
    }
    vector<int>minimum(boundaries+1,length+1);
    vector<int>maximum(boundaries+1,-1);
    vector<bool>connected(boundaries,false);
    minimum[0]=0;
    maximum[0]=0;
    minimum[boundaries]=length;
    maximum[boundaries]=length;
    int remaining=boundaries;
    for(int drop=1;drop<=n;drop++){
        int bucket=static_cast<int>(position/limit);
        minimum[bucket]=min(minimum[bucket],static_cast<int>(position));
        maximum[bucket]=max(maximum[bucket],static_cast<int>(position));
        // Only the two bucket boundaries next to this drop may improve.
        for(int left=bucket-1;left<=bucket;left++){
            if(left<0||left>=boundaries||connected[left]){
                continue;
            }
            if(maximum[left]>=0&&minimum[left+1]<=length&&
                minimum[left+1]-maximum[left]<=limit){
                connected[left]=true;
                remaining--;
            }
        }
        if(remaining==0){
            cout<<drop<<'\n';
            return 0;
        }
        position=(position*multiplier+increment)%(length+1LL);
    }
    cout<<-1<<'\n';
}