Cook and Porridge (Codeforces 1945G)
Tags: Implement, binary search

Finally, lunchtime!$$$n$$$ schoolchildren have lined up in a long queue at the cook's tent for porridge. The cook will be serving porridge for $$$D$$$ minutes. The schoolchild standing in the $$$i$$$-th position in the queue has a priority of $$$k_i$$$ and eats one portion of porridge in $$$s_i$$$ minutes.At the beginning of each minute of the break, the cook serves the first schoolchild in the queue one portion of porridge, after which the schoolchild goes to eat their portion. If the $$$i$$$-th schoolchild is served a portion at the beginning of the $$$x$$$-th minute, then they will return to the queue at the end of the $$$(x + s_i)$$$-th minute.When the $$$i$$$-th schoolchild returns to the queue, the schoolchildren at the end of the queue whose priority is strictly lower than that of the $$$i$$$-th schoolchild must let them pass. Thus, they will stand in the queue behind the last schoolchild whose priority is not lower than their own. That is, behind the last schoolchild $$$j$$$ with $$$k_j \ge k_i$$$. If there is no such schoolchild in the queue, the $$$i$$$-th schoolchild will stand at the front of the queue.If several schoolchildren return at the same time, they will return to the queue in ascending order of their $$$s_i$$$.For example, if $$$n = 3$$$, $$$D = 3$$$, $$$k = [2, 3, 2]$$$, and $$$s = [2, 1, 3]$$$, the serving will occur as follows:  At the beginning of minute $$$1$$$, the students in the queue are $$$[1, 2, 3]$$$, and student $$$1$$$ is served porridge;  at the beginning of minute $$$2$$$, the students in the queue are $$$[2, 3]$$$, and student $$$2$$$ is served porridge;  at the beginning of minute $$$3$$$, the student in the queue is $$$[3]$$$, and student $$$3$$$ is served porridge;  at the end of minute $$$3$$$, student $$$2$$$ returns to the queue, and the queue becomes $$$[2]$$$;  at the end of minute $$$3$$$, student $$$1$$$ returns to the queue, and the queue becomes $$$[2, 1]$$$, as his priority is lower. Determine the minimum number of minutes after the start of the break that each schoolchild will receive porridge at least once, or report that this will not happen within $$$D$$$ minutes.

Input: Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. This is followed by a description of the test cases.The first line of each test case contains two integers $$$n$$$ and $$$D$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le D \le 3\cdot 10^5$$$) — the number of schoolchildren in the queue and the break time, respectively.The next $$$n$$$ lines contain two integers $$$k_i$$$ and $$$s_i$$$ ($$$1 \le k_i, s_i, \le 10^9$$$) — the priority and the time to eat one portion of porridge for the respective schoolchild. The schoolchildren are given in the order they stand in the queue (from the front to the end).It is guaranteed that the sum of the values of $$$n$$$ for all input data sets does not exceed $$$2\cdot 10^5$$$. Similarly, it is guaranteed that the sum of the values of $$$D$$$ for all input data sets does not exceed $$$3\cdot 10^5$$$.

Output: For each test case, output the minimum number of minutes after which each schoolchild will receive porridge at least once. If this does not happen within the break time, output $$$-1$$$.


Sample Inputs:
7
3 3
2 2
3 1
2 3
5 10
10 3
7 1
11 3
5 1
6 1
5 20
4 2
7 2
8 5
1 5
3 1
5 17
1 3
8 2
8 3
2 2
1 1
5 14
8 2
4 2
1 3
8 3
6 4
1 11
4 5
5 14
8 2
4 2
1 3
8 3
6 4

Sample Outputs:
3
-1
12
6
6
1
6

Solution (Python):
import sys
from heapq import heappop, heappush
input = lambda : sys.stdin.readline().rstrip()

def solve_case():
    (n, d) = map(int, input().split())
    k = [0] * n
    s = [0] * n
    for i in range(n):
        (k[i], s[i]) = map(int, input().split())
    k_max_suffix = [0] * n
    k_max_suffix[n - 1] = k[n - 1]
    for i in range(n - 2, -1, -1):
        k_max_suffix[i] = max(k_max_suffix[i + 1], k[i])
    served = 0
    queue = []
    waiting_to_rejoin = []
    for t in range(1, d + 1):
        if queue and -queue[0][0] > k_max_suffix[served]:
            (_, _, _, idx) = heappop(queue)
        else:
            idx = served
            served += 1
            if served == n:
                return t
        heappush(waiting_to_rejoin, (t + s[idx], idx))
        while waiting_to_rejoin and waiting_to_rejoin[0][0] == t:
            (_, idx) = heappop(waiting_to_rejoin)
            heappush(queue, (-k[idx], t, s[idx], idx))
    return -1
ans = []
for _ in range(int(input())):
    ans += [str(solve_case())]
print('\n'.join(ans))

Solution (Python):
import sys
import random
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from collections import defaultdict, Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, insort_left, insort_right

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

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

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

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

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

def primeFactors(n):
    i = 2
    primfac = []
    while i * i <= n:
        while n % i == 0:
            primfac.append(i)
            n = n / i
        i = i + 1
    if n > 1:
        primfac.append(int(n))
    return primfac

def prime_sieve(n):
    is_prime = [True for _ in range(n + 1)]
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            j = i * i
            while j <= n:
                is_prime[j] = False
                j += i
        i += 1
    return is_prime

def find_divisors(number):
    divisors = []
    for i in range(1, int(number ** 0.5) + 1):
        if number % i == 0:
            divisors.append(i)
            if i != number // i:
                divisors.append(number // i)
    return divisors

def solve():
    (n, d) = ints()
    vals = []
    for i in range(n):
        (a, b) = ints()
        vals.append((a, b))
    mma = [0] * n
    mma[-1] = vals[-1][0]
    for i in range(n - 2, -1, -1):
        mma[i] = max(mma[i + 1], vals[i][0])
    new = []
    left = 0
    ss = []
    i = 1
    while i < d + 1 and left < n:
        xx = False
        if len(ss) > 0:
            xx = ss[0]
        if xx == False or mma[left] >= abs(xx[0]):
            heappush(new, (i + vals[left][1], vals[left][1], left + 1))
            left += 1
            if left >= n:
                return i
        else:
            heappop(ss)
            heappush(new, (i + vals[xx[3] - 1][1], vals[xx[3] - 1][1], xx[3]))
        while new and new[0][0] == i:
            heappush(ss, (-vals[new[0][2] - 1][0], i, vals[new[0][2] - 1][1], new[0][2]))
            heappop(new)
        i += 1
    return -1

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))
if __name__ == '__main__':
    for _ in range(get_int()):
        print(solve())

Solution (Python):
import heapq
t = int(input())
for _i in range(t):
    (n, d) = map(int, input().split())
    students = []
    for i in range(n):
        (k, s) = map(int, input().split())
        students.append((k * -1, s))
    to_add = [[] for _ in range(d + 1)]
    p = 0
    suffix_max = [0] * n
    suffix_max[n - 1] = students[n - 1][0]
    for i in range(n - 2, -1, -1):
        suffix_max[i] = min(students[i][0], suffix_max[i + 1])
    heap = []
    heapq.heapify(heap)
    ans = -1
    for current_sec in range(1, d + 1):
        max_prior_heap = 0
        if len(heap):
            max_prior_heap = heap[0][0]
        if suffix_max[p] > max_prior_heap:
            (k, t, s) = heapq.heappop(heap)
            student = (k, s)
        else:
            student = students[p]
            p += 1
        if current_sec + student[1] <= d:
            to_add[current_sec + student[1]].append(student)
        if p == n:
            ans = current_sec
            break
        for student in to_add[current_sec]:
            heapq.heappush(heap, (student[0], current_sec, student[1]))
    print(ans)