IOI '04 P6 - Empodia

#include <iostream>
#include <vector>
#include <stack>
#include <climits>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    // For each index i, find smallest j s.t. j > i and a[j] < a[i]
    vector<int> nextSmaller(n, n);
    stack<int> st;
    for (int i = n-1; i >= 0; --i) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        if (!st.empty()) nextSmaller[i] = st.top();
        st.push(i);
    }

    // Find smallest framed interval starting at each index
    vector<pair<int, int>> candidates; // framed intervals

    stack<int> maximums; // maximums since start
    // Let dif[i] = a[i] - i
    vector<vector<int>> maxByDif(2*n-1); // -(n-1) to n-1
    auto dif = [&](int i) { // adding n-1 to avoid negatives
        return a[i] - i + n-1;
    };

    for (int s = n-1; s >= 0; --s) { // fix start
        // remove old maximums
        while (!maximums.empty() && a[maximums.top()] <= a[s]) {
            maxByDif[dif(maximums.top())].pop_back();
            maximums.pop();
        }

        if (!maxByDif[dif(s)].empty()) {
            // first max since i with dif[j] = dif[i]
            int r = maxByDif[dif(s)].back();
            if (r < nextSmaller[s]) candidates.emplace_back(s, r);
        }

        // add new maximum
        maximums.push(s);
        maxByDif[dif(s)].push_back(s);
    }

    // Remove all framed intervals that contain others
    //  intervals are ordered by left in decreasing order, and have distinct lefts
    stack<pair<int, int>> empodia;
    int closestFinish = INT_MAX;
    for (auto [l, r] : candidates) {
        if (closestFinish > r) {
            empodia.emplace(l, r);
            closestFinish = r;
        }
    }

    // Print empodia
    cout << empodia.size() << endl;
    while (!empodia.empty()) {
        cout << 1+empodia.top().first << ' ' << 1+empodia.top().second << '\n';
        empodia.pop();
    }
    return 0;
}