Proficient.
Put your skills to the test.

Problem summary

Axis-aligned rectangles stand consecutively from x=0 on the x-axis. Count input points inside their union, including its boundary; repeated input points count separately.

Constraints

1 ≤ N ≤ 10,000; 1 ≤ M ≤ 100,001; 1 ≤ width,height ≤ 10,000; 0 ≤ x,y ≤ 1,000,000.

Worked example

An independently prepared example for this explanation.

1 4
2 3
1 2
3 7
1 2
0 3

3

Solution analysis

1. Prefix sums of rectangle widths give their right boundaries. For a point x, lower_bound finds the first right boundary at least x. This rectangle is the only possible containing rectangle, except on a shared vertical boundary.
2. At a shared boundary, both neighboring rectangles include the point. Compare y with the larger of their heights. At x=0 only the first rectangle applies; at the final right boundary only the last applies.
3. In official example 2 the union is [0,2]×[0,3]. The point (1,2) is supplied twice and both occurrences count, while (0,3) is on the boundary. Thus the answer is 3.

Why it works

A point strictly between consecutive width-prefix boundaries belongs horizontally to exactly one rectangle, and the height comparison exactly checks vertical membership. At a shared boundary the union contains heights up to the larger adjacent height. The algorithm checks these exhaustive cases and counts each supplied point once.

Watch out. A shared boundary can belong to the taller rectangle on either side. Keep duplicate points. Do not accept x beyond the total width.

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,m;
    cin>>n>>m;
    vector<int>right(n),height(n);
    int total=0;
    for(int i=0;i<n;i++){
        int width;
        cin>>width>>height[i];
        total+=width;
        right[i]=total;
    }
    int answer=0;
    while(m--){
        int x,y;
        cin>>x>>y;
        auto it=lower_bound(right.begin(),right.end(),x);
        if(it==right.end()){
            continue;
        }
        int index=static_cast<int>(it-right.begin());
        int ceiling=height[index];
        // Both closed rectangles contribute at their shared boundary.
        if(right[index]==x&&index+1<n){
            ceiling=max(ceiling,height[index+1]);
        }
        answer+=y<=ceiling;
    }
    cout<<answer<<'\n';
}