Let's sort the array in nonincreasing order. Now the answer is some of the first containers. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: $$$\mathcal{O}(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

Note that for each question, the resulting array is

So, the sum of the elements of the new array after each question is

We can compute $$$a_1+⋯+a_{l−1}$$$ and $$$a_{r+1}+⋯+a_n$$$ in $$$\mathcal{O}(1)$$$ time by precomputing the sum of all prefixes and suffixes, or alternatively by using the prefix sums technique. So we can find the sum each time in $$$\mathcal{O}(1)$$$ per question, and just check if it's odd or not. The time complexity is $$$\mathcal{O}(n+q)$$$.

from itertools import accumulate
from sys import stdin


# Fast input for python. Note that it gives you the input with the newline character, '\n'
# This may cause a problem on string problems. In that case, use stdin.readline()[:-1] to strip the last character('\n')
def input(): return stdin.readline()


T = int(input())
for _ in range(T):
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))

    pref_sum = list(accumulate(a, initial=0))

    for __ in range(Q):
        l, r, k = map(int, input().split())
        left_sum = pref_sum[l - 1]
        right_sum = pref_sum[-1] - pref_sum[r]
        middle_sum = k*(r - l + 1)
        total_sum = left_sum + middle_sum + right_sum

        if total_sum%2 == 1:
            print("YES")
        else:
            print("NO")  

The key observation is that to choose an element $$$b_i$$$, we need to consider all elements $$$b_j$$$ where $$$j < i$$$. The objective is to select consecutive elements starting from the first element to maximize the cumulative sum. This principle applies to both the $$$r$$$ and $$$b$$$ sequences.

we can compute the prefix sum for both $$$r$$$ and $$$b$$$. To determine the optimal reconstruction of the original sequence $$$a$$$, we add the maximum prefix sum values from both the $$$r$$$ and $$$b$$$ sequences.

import itertools

t = int(input())

for _ in range(t):
    n = int(input())
    r = list(map(int, input().split()))
    m = int(input())
    b = list(map(int, input().split()))

    r = list(itertools.accumulate(r))
    b = list(itertools.accumulate(b))

    result = max(0, max(r)) + max(0, max(b))
    print(result)

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use normal line sweep to store cumulative sums. Finally sort both arrays (the prefix sum array and the main array) and sum the product of the elements on the same index from both arrays.

Time complexity: $$$\mathcal{O}(nlogn)$$$.

Memory complexity: $$$\mathcal{O}(n)$$$.

from itertools import accumulate
from sys import stdin


def input(): return stdin.readline()


N, Q = map(int, input().split())
nums = sorted(map(int, input().split()))

line = [0]*(N + 1)
for _ in range(Q):
    l, r = map(int, input().split())
    line[l - 1] += 1
    line[r] -= 1

counts = sorted(accumulate(line[:-1]))

ans = 0
for i in range(N):
    ans += counts[i]*nums[i]

print(ans)

Let the sum of elements from the beginning be $$$p_i$$$. $$$[l,r]$$$ is bad if the sum of all the elements between that range equals $$$r - l + 1$$$. so $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$.

Rewrite the formula $$$pr−pl + 1 = r−l + 1$$$.

Let's precalculate the array $$$p$$$, where $$$pi=\sum\limits_{j = 0}^{i - 1} a_j$$$(so $$$p_x$$$ is the sum of the first $$$x$$$ elements of $$$a$$$). Then subarray $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$, so $$$pr−r=pl−l$$$.

Thus, we have to group all prefixes by value $$$pi−i$$$ for $$$i$$$ from $$$0$$$ to $$$n$$$. And if x indexes have a prefix with the same value of $$$pi−i$$$ then we have to add $$$x(x−1)/2$$$ to the answer.

from collections import defaultdict
testcases = int(input())
for _ in range(testcases):
    n = int(input())
    a = input()
    d = defaultdict(int)
    d[0] = 1
    res, s = 0, 0
    
    for i in range(n):
        s += int(a[i])
        x = s - i - 1
        d[x] += 1
        
        res += d[x] - 1
        
    print(res)