Барок 2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll min(ll a, ll b, ll c, ll d)
{
    return min(a, min(b, min(c, d)));
}

ll max(ll a, ll b, ll c, ll d)
{
    return max(a, max(b, max(c, d)));
}

template <typename T>
int cmp(T& a, T& b)
{
    if(a < b)
    {
        return -1;
    }
    else if(a > b)
    {
        return 1;
    }
    return 0;
}

class Segment
{
public:
    ll left, right;

    Segment(ll left = 0LL, ll right = 0LL)
    {
        this->left = left;
        this->right = right;
    }

    bool intersectsWith(const Segment& other)
    {
        bool thisCheck = (left >= other.left && left <= other.right) || (right >= other.left && right <= other.right);
        bool otherCheck = (other.left >= left && other.left <= right) || (other.right >= left && other.right <= right);
        return thisCheck || otherCheck;
    }

    Segment getUnion(const Segment& other)
    {
        ll uLeft = min(left, right, other.left, other.right);
        ll uRight = max(left, right, other.left, other.right);
        return Segment(uLeft, uRight);
    }

    ll getLength()
    {
        return right - left + 1;
    }

    string toString()
    {
        stringstream ss;
        ss<<"{"<<left<<", "<<right<<"}";
        return ss.str();
    }

    bool operator <(const Segment& other) const
    {
        int res = cmp(left, other.left);
        if(res == 0)
        {
            res = cmp(right, other.right);
        }
        return res < 0;
    }

    bool operator >(const Segment& other) const
    {
        int res = cmp(left, other.left);
        if(res == 0)
        {
            res = cmp(right, other.right);
        }
        return res > 0;
    }

    bool operator ==(const Segment& other) const
    {
        int res = cmp(left, other.left);
        if(res == 0)
        {
            res = cmp(right, other.right);
        }
        return res == 0;
    }
};

const int TYPE_RECT_BEGIN = 0;
const int TYPE_RECT_END = 1;

class Rectangle {
public:
    Segment horizontalSegment;
    Segment verticalSegment;

    Rectangle(ll topLeftX, ll topLeftY, ll bottomRightX, ll bottomRightY)
    {
        horizontalSegment = Segment(topLeftX, bottomRightX);
        verticalSegment = Segment(topLeftY, bottomRightY);
    }

    string toString()
    {
        stringstream ss;
        ss<<"Horizontal: "<<horizontalSegment.toString()<<"\tVertical: "<<verticalSegment.toString();
        return ss.str();
    }
};

class Event {
public:
    int type;
    ll x;
    Segment verticalSegment;

    Event(int type, ll x, Segment verticalSegment)
    {
        this->type = type;
        this->x = x;
        this->verticalSegment = verticalSegment;
    }
};

bool horizontalPosCmp(const Event& first, const Event& second)
{
    int res = cmp(first.x, second.x);
    if(res == 0)
    {
        res = cmp(first.type, second.type);
    }
    if(res == 0)
    {
        res = cmp(first.verticalSegment, second.verticalSegment);
    }
    return res < 0;
}

vector<Segment> getUnion(vector<Segment> &verticalSegments)
{
    vector<Segment> res;
    vector<bool> used(verticalSegments.size(), false);
    for(int i = 0;i<verticalSegments.size();++i)
    {
        if(!used[i])
        {
            used[i] = true;
            Segment current = verticalSegments[i];
            for(int j = i+1;j<verticalSegments.size();++j)
            {
                if(current.intersectsWith(verticalSegments[j]))
                {
                    used[j] = true;
                    current = current.getUnion(verticalSegments[j]);
                }
            }
            res.push_back(current);
        }
    }
    return res;
}

ll getArea(ll width, vector<Segment> &verticalSegments)
{
    ll res = 0;
    vector<Segment> segmentUnion = getUnion(verticalSegments);
    for(Segment& segment: segmentUnion)
    {
        res += width * segment.getLength();
    }
    return res;
}

vector<Segment> keysToVector(map<Segment, int> &segments)
{
    vector<Segment> res;
    for(auto it = segments.begin(); it != segments.end(); ++it)
    {
        if(it->second != 0)
        {
            res.push_back(it->first);
        }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);

    ll height, width;
    cin>>height>>width;

    int months;
    cin>>months;

    int buildings;
    cin>>buildings;

    vector<Event> events;
    for(int i = 0;i<buildings;++i)
    {
        ll x, y;
        cin>>y>>x;
        ll topX = max(1LL, x - months);
        ll topY = max(1LL, y - months);
        ll bottomX = min(width, x + months);
        ll bottomY = min(height, y + months);
        Rectangle rectangle(topX, topY, bottomX, bottomY);
        events.push_back(Event(TYPE_RECT_BEGIN, rectangle.horizontalSegment.left, rectangle.verticalSegment));
        events.push_back(Event(TYPE_RECT_END, rectangle.horizontalSegment.right+1, rectangle.verticalSegment));
    }
    sort(events.begin(), events.end(), horizontalPosCmp);

    map<Segment, int> segments;
    ll prevX = 0;
    ll res = 0;
    for(int i = 0;i<events.size();++i)
    {
        Event &event = events[i];

        if(i > 0)
        {
            // Add area
            vector<Segment> segmentVector = keysToVector(segments);
            res += getArea(event.x - prevX, segmentVector);
        }

        while(events[i].x == event.x && i < events.size())
        {
            // While there are events on this position, process them
            if(events[i].type == TYPE_RECT_BEGIN)
            {
                // Add vertical segment
                segments[events[i].verticalSegment]++;
            }
            else
            {
                // Remove the vertical segment
                segments[events[i].verticalSegment]--;
            }
            i++;
        }
        i--;
        prevX = event.x;
    }
    cout<<res<<endl;
    return 0;
}