1. Идея

Нужно найти любой подотрезок массива, сумма которого равна S.

Для таких задач удобно использовать префиксные суммы.

Обозначим:

• pref[r] — сумма первых r элементов,
• тогда сумма на подотрезке от l до r равна pref[r] - pref[l - 1].

Значит, для каждого правого конца r нам нужно понять, существует ли такой индекс l - 1, что

pref[r] - pref[l - 1] = S

откуда

pref[l - 1] = pref[r] - S.

То есть при просмотре массива слева направо достаточно хранить уже встреченные значения префиксных сумм в словаре: если раньше уже была сумма pref[r] - S, то нужный подотрезок найден.

2. Наблюдения

Наблюдение 1

Сумма подотрезка l..r выражается через префиксные суммы так:

sum(l..r) = pref[r] - pref[l - 1].

Это стандартное преобразование позволяет заменить поиск суммы подотрезка на поиск пары префиксных сумм.

Наблюдение 2

Если в текущей позиции r префиксная сумма равна pref, то нам нужен ранее встреченный префикс need = pref - S.

Если такой префикс уже был в позиции p, то:

• pref[p] = need,
• значит сумма элементов от p + 1 до r равна S.

Тогда ответ:

• l = p + 1,
• r = r.

Наблюдение 3

Нужно не забыть про подотрезки, начинающиеся с первого элемента.

Для этого заранее считаем, что префиксная сумма 0 встречалась в позиции 0.
Это означает: до начала массива сумма равна 0.

Тогда если pref[r] = S, то

• need = pref[r] - S = 0,
• словарь уже содержит 0 -> 0,
• получаем подотрезок 1..r.

Наблюдение 4

Элементы массива могут быть отрицательными, поэтому метод двух указателей здесь не подходит.
Именно поэтому нужен подход через префиксные суммы и словарь.

3. Алгоритм

1. Считываем n, S и массив.
2. Создаём словарь first_pos, где:
   • ключ — значение префиксной суммы,
   • значение — первая позиция, где она встретилась.
3. Изначально кладём first_pos[0] = 0.
4. Идём по массиву слева направо, поддерживая текущую префиксную сумму pref.
5. Для каждой позиции r:
   • прибавляем текущий элемент к pref,
   • считаем need = pref - S,
   • если need уже есть в словаре, то найден ответ:
     • l = first_pos[need] + 1,
     • выводим l и r.
6. Если текущая префиксная сумма pref ещё не встречалась, сохраняем её в словарь.
7. Если после прохода по массиву ответ не найден, выводим -1.

4. Почему это работает

Докажем корректность алгоритма.

Пусть на некотором шаге мы находимся в позиции r, и текущая префиксная сумма равна pref[r].

Мы ищем подотрезок с суммой S, оканчивающийся в r.
Для подотрезка l..r его сумма равна:

pref[r] - pref[l - 1].

Чтобы она была равна S, необходимо и достаточно, чтобы:

pref[l - 1] = pref[r] - S.

Именно это значение мы обозначаем как need.

• Если need уже встречалось раньше в позиции p, то:

  • pref[p] = need,
  • значит сумма на подотрезке p + 1 .. r равна S,
  • следовательно, можно вывести l = p + 1, r.

• Если need не встречалось, то ни один подотрезок, заканчивающийся в r, не подходит.

Так мы проверяем все возможные правые границы r от 1 до n.
Если существует хотя бы один подходящий подотрезок, то при обработке его правой границы нужный префикс уже будет находиться в словаре, и алгоритм его найдёт.

Если же алгоритм дошёл до конца и не нашёл ответ, значит для ни одной позиции r не существовало подходящего l, следовательно, подотрезка с суммой S в массиве нет.

Значит, алгоритм корректен.

5. Сложность

Для каждой позиции выполняется константное число операций со словарём.

• Время: O(n) в среднем.
• Память: O(n).

Это подходит для n до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    unordered_map<long long, int> first_pos;
    first_pos[0] = 0;

    long long pref = 0;

    for (int r = 1; r <= n; r++) {
        pref += a[r];

        long long need = pref - S;
        auto it = first_pos.find(need);
        if (it != first_pos.end()) {
            int l = it->second + 1;
            cout << l << " " << r << "\n";
            return 0;
        }

        if (first_pos.find(pref) == first_pos.end()) {
            first_pos[pref] = r;
        }
    }

    cout << -1 << "\n";
    return 0;
}

7. Код на Python 3

n, S = map(int, input().split())
a = list(map(int, input().split()))

first_pos = {0: 0}
pref = 0

for r in range(1, n + 1):
    pref += a[r - 1]
    need = pref - S
    if need in first_pos:
        l = first_pos[need] + 1
        print(l, r)
        break
    if pref not in first_pos:
        first_pos[pref] = r
else:
    print(-1)