Proficient.
Put your skills to the test.

Problem summary

A rigid cleaning board spans the corridor height. Its damaged right boundary is an orthogonal polyline. Slide the board left until it leaves; find the area never covered by the board.

Constraints

1 < N ≤ 100000; w,h ≤ 1100000000; 0 ≤ x ≤ w; 0 ≤ y ≤ h.

Worked example

An independently prepared example for this explanation.

15 10
16
6 0
6 2
11 2
11 6
8 6
8 4
9 4
9 5
10 5
10 3
6 3
6 7
12 7
12 8
9 8
9 10

58

Solution analysis

1. Fix a horizontal height y away from vertices. During the leftward slide, the board covers every corridor position from x=0 up to the largest x-coordinate at which its initial boundary crosses this horizontal line. Let that envelope be reach(y). The dirty width is w−reach(y).
2. Each vertical boundary segment contributes a constant candidate x over its y interval. Create add/remove events at its normalized y endpoints and sweep upward through these events. A multiset stores active x-coordinates, whose maximum is the current reach. Horizontal boundary pieces affect only a zero-area set.
3. In the sample, the envelope values over successive height ranges are 6 on [0,2], 11 on [2,6], 6 on [6,7], 12 on [7,8], and 9 on [8,10]. The cleaned area is 92, leaving 150−92=58.

Why it works

At each height, every initially occupied interval slides continuously toward negative x, sweeping all positions up to its rightmost endpoint. Their union therefore reaches exactly the maximum boundary crossing. The multiset contains exactly the vertical segments crossing each open sweep strip, so its maximum gives that reach. Summing dirty strip widths times heights integrates the required area.

Watch out. The boundary can move upward as well as downward. Integrating signed individual segments or assuming y-monotonicity is incorrect. Use 64-bit area products.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
// Algorithm: Fix a horizontal height y away from vertices.
using namespace std;
struct Event{
    long long y,x;
    int change;
    bool operator<(const Event&other)const{
        return y<other.y;
    }
};
int main(){
    long long width,height;
    int n;
    cin>>width>>height>>n;
    vector<pair<long long,long long>>points(n);
    for(auto&point:points){
        cin>>point.first>>point.second;
    }
    vector<Event>events;
    for(int i=1;i<n;++i){
        if(points[i].first!=points[i-1].first||points[i].second==points[i-1].second){
            continue;
        }
        long long low=min(points[i].second,points[i-1].second);
        long long high=max(points[i].second,points[i-1].second);
        events.push_back({low,points[i].first,1});
        events.push_back({high,points[i].first,-1});
    }
    sort(events.begin(),events.end());
    multiset<long long>active;
    long long previousY=0,dirty=0;
    size_t i=0;
    while(i<events.size()){
        long long y=events[i].y;
        long long reach=active.empty()?0:*active.rbegin();
        dirty+=(width-reach)*(y-previousY);
        while(i<events.size()&&events[i].y==y){
            if(events[i].change==1){
                active.insert(events[i].x);
            }
            else{
                active.erase(active.find(events[i].x));
            }
            ++i;
        }
        previousY=y;
    }
    dirty+=width*(height-previousY);
    cout<<dirty<<'\n';
}