ATM and Students (Codeforces 1611F)
Tags: Others, two pointers

Polycarp started working at a bank. He was assigned to monitor the ATM. The ATM initially contains $$$s$$$ rubles.A queue of $$$n$$$ students lined up to him. Each student wants to either withdraw a certain amount of money or deposit it into an account. If $$$a_i$$$ is positive, then the student credits that amount of money via ATM. Otherwise, the student withdraws $$$|a_i|$$$ rubles.In the beginning, the ATM is turned off and an arbitrary number of students are not served. At some point, Polycarp turns on the ATM, which has an initial amount of $$$s$$$ rubles. Then, the remaining students start queueing at the ATM. If at some point in time there is less money in the ATM than the student wants to withdraw, then the student is not served and Polycarp turns off the ATM and does not turn it on anymore.More formally, the students that are served are forming a contiguous subsequence.Polycarp wants the ATM to serve the maximum number of students. Help him in this matter. Print the numbers of the first and last student, or determine that he will not be able to serve anyone.In other words, find such a longest continuous segment of students that, starting with the sum of $$$s$$$ at the ATM, all these students will be served. ATM serves students consistently (i.e. one after another in the order of the queue).

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of two lines. The first one contains integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 2\cdot10^5$$$; $$$0 \le s \le 10^9$$$) — the length of the $$$a$$$ array and the initial amount of rubles in the ATM. The second contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — elements of the $$$a$$$ array. Note that $$$a_i$$$ can be zero.It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: Print $$$t$$$ lines, each line must contain the answer to the corresponding set of input data: if the answer exists, print the numbers of the first and last served student. If there is no solution, then print -1 on the line.If there are several possible answers, print any.

Note: In the first test case, the only correct answer is 2 4, since when serving students, the number of rubles at the ATM does not become negative, and this is the maximum number of students that can be served.In the second test case, the answer is -1, as there is not enough money for any student at the ATM.In the third test case, the answer can be either 1 2 or 4 5.

Sample Inputs:
3
4 10
-16 2 -6 8
3 1000
-100000 -100000 -100000
6 0
2 6 -164 1 -1 -6543

Sample Outputs:
2 4
-1
1 2

Solution (Python):
import io
import os
import collections
import math
import functools
import itertools
import bisect
import heapq
from sys import stdin, stdout, stderr, setrecursionlimit
from collections import *
from math import *
from functools import *
from itertools import *
from heapq import *
from bisect import bisect_left, bisect_right, insort_left, insort_right
setrecursionlimit(1000000)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_ints():
    return list(map(int, input().split()))

def get_int():
    return int(input())

def get_str():
    return ''.join(list(map(chr, input().rstrip())))

def eprint(*args):
    stderr.write(', '.join(map(str, args)) + '\n')

def print(*args):
    stdout.write(' '.join(map(str, args)) + '\n')

def solve():
    (n, s) = get_ints()
    arr = get_ints()
    balance = s
    start = 0
    max_start = -1
    max_length = 0
    for (end, num) in enumerate(arr):
        balance += num
        while balance < 0:
            balance -= arr[start]
            start += 1
        length = end - start + 1
        if length > max_length:
            max_length = length
            max_start = start
    if max_start == -1:
        print('-1')
    else:
        print(str(max_start + 1) + ' ' + str(max_start + max_length))
T = get_int()
for _ in range(T):
    solve()

Solution (Python):
import sys
import math
import bisect
import heapq
import itertools
from itertools import accumulate
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 1000000007

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_list():
    return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
    return sys.stdin.readline().strip()

def get_int():
    return int(sys.stdin.readline().strip())

def get_list_strings():
    return list(map(str, sys.stdin.readline().strip().split()))

def solve():
    (n, current) = get_ints()
    nums = get_list()
    answer = 0
    output = []
    left = 0
    for right in range(n):
        current += nums[right]
        while left < n and current < 0:
            current -= nums[left]
            left += 1
        if answer < right - left + 1:
            answer = right - left + 1
            output = [left + 1, right + 1]
    return output if output else [-1]
if __name__ == '__main__':
    for i in range(get_int()):
        print(*solve())

Solution (Python):
import copy
import random
import heapq
import math
import sys
import bisect
import datetime
from functools import lru_cache
from collections import deque
from collections import Counter
from collections import defaultdict
from itertools import combinations
from itertools import permutations
from types import GeneratorType
from functools import cmp_to_key
from functools import reduce
from operator import xor
from operator import mul
from operator import add
from heapq import nlargest
inf = float('inf')

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(' '.join((str(w) for w in x)) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc

def main(ac=FastIO()):
    for _ in range(ac.read_int()):
        (n, s) = ac.read_ints()
        a = ac.read_list_ints()
        ans = j = pre = 0
        lst = [-1]
        for i in range(n):
            while j < n and pre + a[j] >= -s:
                pre += a[j]
                j += 1
            if j - i > ans:
                ans = j - i
                lst = [i + 1, j]
            pre -= a[i]
        ac.lst(lst)
    return
main()