IOI '07 P3 - Sails

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>

using namespace std;

int H = 0;

struct Segment {
    int bottom, top;
    Segment() {}
    Segment(int mn, int mx): bottom(mn), top(mx) {}
    bool operator < (const Segment &s2) const {
        return pair<int, int>(bottom, top) < pair<int, int>(s2.bottom, s2.top);
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> masts(n);
    for (auto &[h, k] : masts) cin >> h >> k, H = max(H, h);
    sort(masts.begin(), masts.end());

    set<Segment> segments; // segments of heights with equal number of sails
    segments.emplace(1, H);

    vector<int> adjDifference(1+H+1); // between number of sails on each height
    auto rangeIncrement = [&adjDifference](int first, int last) { // [first, last)
        ++adjDifference[first];
        --adjDifference[last];
    };

    for (auto [h, k] : masts) {
        // add 1 to suffix of heights from h to h-k+1, but move the increments
        // in the last (partially covered) segment to the end of that segment
        auto it = segments.lower_bound({h-k+1, H+1});

        if (it != segments.begin()) {
            --it;
            int c = k - max(h - it->top, 0); // number in last segment
            assert(c > 0);

            // reposition to end
            //  +1 in range [it->bottom, it->bottom+c)
            rangeIncrement(it->bottom, it->bottom+c);
            k -= c;

            // update segments
            int f1 = it->bottom, l1 = it->bottom+c-1;
            int f2 = it->bottom+c, l2 = it->top;
            it = segments.erase(it);
            if (f2 <= l2) it = segments.emplace(f2, l2).first;

            if (f1 > 1 && !adjDifference[f1]) { // incremented segment has equal value with previous segment
                // merge
                --it;
                int oldFirst = it->bottom;
                assert(it->top+1 == f1);
                segments.erase(it);
                segments.emplace(oldFirst, l1);
            } else segments.emplace(f1, l1);
        }

        if (k) {
            // +1 in range [h-k+1, h]
            rangeIncrement(h-k+1, h+1);

            //  update segments
            it = prev(segments.end());
            if (h >= it->bottom && h < H) { // need to split 0 segment
                int b = it->bottom;
                segments.erase(it);
                segments.emplace(b, h);
                segments.emplace(h+1, H);
            }

            it = segments.lower_bound({h-k+1, 0}); // first updated segment
            //   if it and prev(it) are now equal, merge them
            if (it->bottom > 1 && !adjDifference[it->bottom]) {
                // merge
                int last = it->top;
                it = prev(segments.erase(it));
                int first = it->bottom;
                segments.erase(it);
                segments.emplace(first, last);
            }
        }
    }

    // Determine the total inefficiency of the configuration
    long long totalInefficiency = 0;
    for (int h = 1, sails = 0; h <= H; ++h) {
        sails += adjDifference[h];
        totalInefficiency += sails*(sails-1LL)/2;
    }
    cout << totalInefficiency << endl;
    return 0;
}