Find B (Codeforces 1923C)
Tags: Greedy, constructive algorithms

An array $$$a$$$ of length $$$m$$$ is considered good if there exists an integer array $$$b$$$ of length $$$m$$$ such that the following conditions hold:   $$$\sum\limits_{i=1}^{m} a_i = \sum\limits_{i=1}^{m} b_i$$$;   $$$a_i \neq b_i$$$ for every index $$$i$$$ from $$$1$$$ to $$$m$$$;   $$$b_i > 0$$$ for every index $$$i$$$ from $$$1$$$ to $$$m$$$. You are given an array $$$c$$$ of length $$$n$$$. Each element of this array is greater than $$$0$$$.You have to answer $$$q$$$ queries. During the $$$i$$$-th query, you have to determine whether the subarray $$$c_{l_{i}}, c_{l_{i}+1}, \dots, c_{r_{i}}$$$ is good.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the length of the array $$$c$$$ and the number of queries.The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).Then $$$q$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the borders of the $$$i$$$-th subarray.Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$; the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each query, print YES if the subarray is good. Otherwise, print NO.You can output each letter of the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will all be recognized as positive responses.


Sample Inputs:
1
5 4
1 2 1 4 5
1 5
4 4
3 4
1 3

Sample Outputs:
YES
NO
YES
NO

Solution (Python):
import sys

def solve() -> None:
    (n, q) = map(int, input().split())
    arr = list(map(int, input().split()))
    pref = [0] * (n + 1)
    cnt1 = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] + arr[i]
        cnt1[i + 1] = cnt1[i] + int(arr[i] == 1)
    ans = []
    for _ in range(q):
        (l, r) = map(int, input().split())
        if l == r:
            ans.append('NO')
            continue
        l -= 1
        r -= 1
        sm = pref[r + 1] - pref[l]
        k = cnt1[r + 1] - cnt1[l]
        length = r - l + 1
        sm -= length - k
        if not k:
            ans.append('YES')
        else:
            ans.append('YES' if k * 2 <= sm else 'NO')
    print('\n'.join(ans) + '\n')
input = sys.stdin.readline
for _ in range(int(input())):
    solve()

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
print = sys.stdout.write

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

def test():
    (n, q) = gai()
    c = gai()
    can_sub = [0] * n
    need_add = [0] * n
    for i in range(n):
        if i == 0:
            if c[i] > 1:
                can_sub[i] += c[i] - 1
            else:
                need_add[i] += 1
        if c[i] > 1:
            need_add[i] = need_add[i - 1]
            can_sub[i] = can_sub[i - 1] + (c[i] - 1)
        else:
            can_sub[i] = can_sub[i - 1]
            need_add[i] = need_add[i - 1] + 1
    for qidx in range(q):
        (li, ri) = gai()
        if li == ri:
            print('NO\n')
            continue
        li -= 1
        ri -= 1
        csq = can_sub[ri] - can_sub[li]
        naq = need_add[ri] - need_add[li]
        if c[li] > 1:
            csq += c[li] - 1
        else:
            naq += 1
        if csq >= naq:
            print('YES\n')
        else:
            print('NO\n')
for _ in range(int(input())):
    test()

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    t = int(input().strip())
    for _ in range(t):
        (n, q) = map(int, input().strip().split())
        c = list(map(int, input().strip().split()))
        tmp = [0] * (n + 1)
        for i in range(n):
            if c[i] == 1:
                tmp[i + 1] = tmp[i] + 1
            else:
                tmp[i + 1] = tmp[i]
        pre = [0] * (n + 1)
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + c[i - 1] - 1
        for _ in range(q):
            (l, r) = map(int, input().strip().split())
            if l == r:
                print('NO')
                continue
            cnt = tmp[r] - tmp[l - 1]
            sum_val = pre[r] - pre[l - 1]
            if sum_val >= cnt:
                print('YES')
            else:
                print('NO')
if __name__ == '__main__':
    main()