POI Task Salad Bar

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

using namespace std;

struct Segment {
    int l, r;
    pair<int, int> mx; // largest on segment: (value, index)
    Segment() {}
    Segment(int i, int v): l(i), r(i), mx(v, i) {}
    bool operator < (const Segment &s2) const {
        return pair<int, int>{l, r} < pair<int, int>{s2.l, s2.r};
    }
    Segment operator + (const Segment &s2) const { // merge two adjacent segments
        assert(r+1 == s2.l);
        Segment s;
        s.l = l, s.r = s2.r;
        s.mx = max(mx, s2.mx);
        return s;
    }
};

int main() {
    int n; string s;
    cin >> n >> s;
    bool allJ = true;
    for (char c : s) {
        if (c == 'p') allJ = false;
    }
    if (allJ) {
        cout << "0\n";
        return 0;
    }

    int ans = 1;
    vector<int> p(1+n);
    for (int i = 1; i <= n; ++i) p[i] = p[i-1] + (s[i-1] == 'p' ? +1 : -1);

    set<Segment> st; // segments of added values
    vector<pair<int, int>> bySize;
    for (int i = 0; i <= n; ++i) bySize.emplace_back(p[i], i);
    sort(bySize.begin(), bySize.end());
    while (!bySize.empty()) {
        auto [v, i] = bySize.back();
        bySize.pop_back();

        // add into set of segments
        Segment seg(i, v);
        auto it = st.lower_bound(seg);
        if (it != st.end() && it->l == i+1) { // merge with next segment
            /*
            consider index i as the element before the start of the substring, with some index k being the end (i, k]
            all indices j between i and the end k of the substring must have p[i] <= p[j] <= p[k]
            maxK = it->r, since next j does not satisfy p[i] <= p[j]
            the other constraint is p[j] <= p[k], so p[k] must be the maximum encountered so far after p[i]
            the last of these will simply be the (rightmost) largest value in the range [i, maxK]
            */
            ans = max(ans, it->mx.second-i);

            // now merge
            seg = seg + *it;
            it = st.erase(it);
        }
        if (it != st.begin()) {
            --it;
            if (it->r == i-1) { // merge with previous segment
                seg = *it + seg;
                st.erase(it);
            }
        }
        st.insert(seg).first;
    }
    cout << ans << endl;
    return 0;
}