HA_63_sybarrays

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <iterator>
using namespace std;

// Класс, поддерживающий скользящее окно
// Оно может:
// - вставлять удалять
// - возвращать максимум
// - получать минимальные разницы между соседями

class SlidingWindow {
public:
    void insert(int x) {
        if (elems.empty()) {
            elems.insert(x);
            return;
        }
        auto it = elems.lower_bound(x);
        if (it != elems.end() && *it == x) {
            // Дублирующиеся значения: разности между одинаковыми = 0,
            // это сразу нарушит условие (т.к. 0 > max невозможно), но
            // всё равно корректно поддержим структуру.
            // Обрабатываем как обычную вставку.
        }
        auto prev = (it == elems.begin()) ? elems.end() : prev_it(it);
        auto next = (it == elems.end()) ? elems.end() : it;

        if (prev != elems.end() && next != elems.end()) {
            // Удаляем старую разницу между prev и next
            long long old_gap = (long long)(*next) - (long long)(*prev);
            auto fg = gaps.find(old_gap);
            if (fg != gaps.end()) gaps.erase(fg);
        }

        if (prev != elems.end()) {
            long long gap = (long long)x - (long long)(*prev);
            gaps.insert(gap);
        }
        if (next != elems.end()) {
            long long gap = (long long)(*next) - (long long)x;
            gaps.insert(gap);
        }

        elems.insert(x);
    }

    void erase(int x) {
        auto it = elems.find(x);
        if (it == elems.end()) return; // нет такого

        auto prev = (it == elems.begin()) ? elems.end() : prev_it(it);
        auto next = next_it(it);

        if (prev != elems.end()) {
            long long gap = (long long)x - (long long)(*prev);
            auto fg = gaps.find(gap);
            if (fg != gaps.end()) gaps.erase(fg);
        }
        if (next != elems.end()) {
            long long gap = (long long)(*next) - (long long)x;
            auto fg = gaps.find(gap);
            if (fg != gaps.end()) gaps.erase(fg);
        }

        if (prev != elems.end() && next != elems.end()) {
            long long new_gap = (long long)(*next) - (long long)(*prev);
            gaps.insert(new_gap);
        }

        elems.erase(it);
    }

    bool empty() const {
        return elems.empty();
    }

    // Возвращает текущий максимум (предполагаем, что не пусто)
    int get_max() const {
        return *elems.rbegin();
    }

    // Возвращает минимальную соседнюю разницу; если <2 элементов, возвращаем бесконечность
    long long min_gap() const {
        if (gaps.empty()) return LLONG_MAX;
        return *gaps.begin();
    }

    size_t size() const {
        return elems.size();
    }

private:
    set<int> elems;
    multiset<long long> gaps;

    // Вспомогательные: безопасно получить prev/next итератор
    set<int>::iterator prev_it(set<int>::iterator it) const {
        return std::prev(it);
    }
    set<int>::iterator next_it(set<int>::iterator it) const {
        auto nxt = std::next(it);
        if (nxt == elems.end()) return elems.end();
        return nxt;
    }
};

pair<int,int> find_best_subarray(const vector<int>& V) {
    int n = V.size();
    SlidingWindow window;
    int bestL = 0, bestR = -1; // пусто
    int l = 0;

    for (int r = 0; r < n; ++r) {
        window.insert(V[r]);

        // Сдвигаем левый указатель, пока условие нарушается
        while (!window.empty()) {
            int current_max = window.get_max();
            long long mg = window.min_gap();
            if (window.size() >= 2 && mg <= current_max) {
                // Нарушается, сдвигаем l
                window.erase(V[l]);
                ++l;
            } else {
                break;
            }
        }

        // Проверка: допустимое окно
        if ((int)window.size() > (bestR - bestL + 1)) {
            // size >=1 всегда удовлетворяет (для size==1: нет пары, условие тривиально)
            bestL = l;
            bestR = r;
        }
    }
    return {bestL, bestR};
}

int main() {
    vector<int> V = {-8, 6, 4, 0, 2, 0, 12, -6, -20, -5, -3, 1, -4};
    auto [l, r] = find_best_subarray(V);
    if (l <= r) {
        cout << "Best subarray: [" << l << ", " << r << "]\n";
        cout << "Elements: ";
        for (int i = l; i <= r; ++i) {
            cout << V[i] << (i < r ? ", " : "\n");
        }
    } else {
        cout << "There is no subarray\n";
    }
    return 0;
}