Expert.
Put your skills to the test.

Problem summary

N raindrops fall in order on a square [0,L]×[0,L]. Find the earliest prefix after which every axis-aligned rectangle of width W and height H contained in the square has a raindrop strictly inside it. Drops on a rectangle boundary do not count. Print −1 if even all drops are insufficient.

Constraints

1≤N≤100000; 1≤L≤10^9; 1≤W,H≤L; 0≤Xi,Yi≤L.

Worked example

Official sample. The thirteenth drop removes the last empty 5×4 rectangle.

14 10 5 4
3 4
0 2
5 1
10 10
4 0
8 7
2 7
6 5
9 2
7 3
5 8
6 5
4 2
3 6

13

Solution analysis

1. Fix the rectangle’s left coordinate x. Only drops with x<Xi<x+W can be inside it horizontally. Sort their Y coordinates together with permanent sentinels 0 and L. An empty vertical interval of height H exists exactly when a gap between consecutive coordinates is at least H. Equality still permits an empty open interior.
2. Sweep x from 0 toward L−W. Maintain a multiset of active Y coordinates and a multiset of adjacent gap lengths. Inserting or removing one Y replaces only its neighboring gaps, so the maximum gap is available in O(1) after O(log N) updates. Duplicate drops are allowed and produce zero-length gaps.
3. Unlike binary searching the time and repeating a full sweep, increase time only when the current x has an empty rectangle. Read the next drop, assigning it to the active heap when x<Xi<x+W, or a pending heap if Xi≥x+W. Drops at Xi≤x and Y=0 or L cannot help any future rectangle in this sweep. Once the current position is covered, continue moving x.
4. Coverage can become worse only when an active drop leaves through the left boundary. Jump to the smallest active Xi, remove all drops with Xi≤x, and activate pending drops with Xi<x+W. Entering drops between jumps can only improve coverage, so no failure is skipped. If the next leaving coordinate exceeds L−W, every remaining position is already covered.
5. The sample requires reading through drop 13 before all swept positions are covered. A smaller illustration is L=4,W=H=3: a single drop at (2,2) lies strictly inside every admissible rectangle and gives answer 1. Conversely a drop at (0,2) lies only on or outside all left boundaries and can never suffice.

Why it works

For any fixed x, consecutive Y gaps characterize every possible empty height-H rectangle. During the sweep, only left-edge exits can increase those gaps; right-edge entries can only decrease them. Thus checking each exit and the initial position covers every real x in the allowed interval. Whenever another drop is read, the previous prefix has a currently witnessed empty rectangle, so it cannot be the answer. Added drops cannot invalidate already covered positions. When the sweep finishes, the current prefix covers all placements and every smaller prefix was disproved, establishing minimality.

Watch out. Use strict horizontal inequalities. A maximum gap equal to H is still uncovered. Remove all coincident X exits together, retain duplicate Y values correctly, and never remove the 0/L sentinels. Reaching the final sweep coordinate is not enough until that position itself is covered.

An independently written complete program with standard headers.

#include<functional>
#include<iostream>
#include<queue>
#include<set>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,length,width,height;
    cin>>n>>length>>width>>height;
    vector<pair<int,int>>drops(n);
    for(auto&[x,y]:drops){
        cin>>x>>y;
    }
    using Point=pair<int,int>;
    priority_queue<Point,vector<Point>,greater<Point>>inside,pending;
    multiset<int>levels{0,length},gaps{length};
    auto addY=[&](int y){
        auto next=levels.lower_bound(y);
        int upper=*next;
        int lower=*prev(next);
        gaps.erase(gaps.find(upper-lower));
        gaps.insert(y-lower);
        gaps.insert(upper-y);
        levels.insert(y);
    };
    auto removeY=[&](int y){
        auto current=levels.find(y);
        int lower=*prev(current);
        int upper=*next(current);
        gaps.erase(gaps.find(y-lower));
        gaps.erase(gaps.find(upper-y));
        gaps.insert(upper-lower);
        levels.erase(current);
    };
    int x=0,used=0;
    while(true){
        // Read more time only when this position witnesses an empty rectangle.
        while(*gaps.rbegin()>=height){
            if(used==n){
                cout<<-1<<'\n';
                return 0;
            }
            auto[dropX,dropY]=drops[used++];
            if(dropY==0||dropY==length||dropX<=x){
                continue;
            }
            if(dropX<x+width){
                inside.push({dropX,dropY});
                addY(dropY);
            }
            else{
                pending.push({dropX,dropY});
            }
        }
        // No active drop leaves before the final possible left boundary.
        if(x==length-width||inside.top().first>length-width){
            cout<<used<<'\n';
            return 0;
        }
        x=inside.top().first;
        while(!inside.empty()&&inside.top().first<=x){
            removeY(inside.top().second);
            inside.pop();
        }
        while(!pending.empty()&&pending.top().first<x+width){
            auto point=pending.top();
            pending.pop();
            if(point.first>x){
                inside.push(point);
                addY(point.second);
            }
        }
    }
}