Error:
time limit exceeded

def solve(a, k):
    N = len(a)
    # s_max contains the max elements of each contiguous subarray
    s_max=[max(a[i:i+j]) for i in range(0,N) for j in range(1,N-i+1)]
    s_max.sort()
    
    l = 0
    r = len(s_max)-1
    while True:
        mid = (r+l)//2
        if mid == l:
            return len(s_max)-r
        elif s_max[mid] <= k:
            l = mid
        else:
            r = mid

def solve(a, k):
    N = len(a)
    if max(a) < k:
        return 0
    if k < min(a):
        return N*(N+1)//2
    cnt = 0
    for ind, val in enumerate(a):
        if val > k:
            # count subarrays where val > k and val=max(subarray) 
            # and val is the rightmost element
            j = ind-1
            left = 1
            while j >= 0 and a[j] <= val:
                left += 1
                j -= 1
            
            # count subarrays where val > k and val=max(subarray) 
            # and val is the leftmost element
            right = 1
            j = ind+1
            while j < N and a[j] <= val:
                right += 1
                j += 1
                
            # total subarrays with max(subarray) > k 
            cnt += left * right    
    return cnt 

Error:
Wrong Answer

• Find recursively the number of subsequences for which j <= N // 2
  
• Find recursively the number of subsequences for which N // 2 <= i
  
• Find by scanning the array, the number of subsequences for which i < N // 2 < j. This can be done by a O(N) scanning of the array similar to what you are doing in the second algorithm
  

def getnum(L, K, a, b):
    if b <= a:
        return 0
    m = (a + b) // 2
    i = next((k for k in range(m-1, a-1, -1) if L[k] > K), a-1)
    j = next((k for k in range(m, b) if L[k] > K), b)
    if j == b:
        if i < a:
            return 0
        else:
            return (i - a + 1) * (b - a) + getnum(L, K, a, i)
    else:
        s = (j - a + 1) * (b - j) + getnum(L, K, j+1, b)
        if i < a:
            return s
        else:
            return s + (i - a + 1) * (j - a) + getnum(L, K, a, i)
        
def solve(L, K):
    return getnum(L, K, 0, len(L))

inp = """\
2
3 2
1 2 3 
3 1
1 2 3
"""

def main():
    import io
    f = io.StringIO(inp)
    ntcase = int(next(f).strip())
    for i in range(ntcase):
        N, K = (int(x) for x in next(f).strip().split())
        L = [int(x) for x in next(f).strip().split()]
        assert(len(L) == N)
        print(solve(L, K))

if __name__ == '__main__':
    main()

def solve(L, K):
    n, s, p = len(L), 0, -1
    for i, x in enumerate(L):
        if x > K:
            s += (i - p) * (n - i)
            p = i
    return s

inp = """\
2
3 2
1 2 3 
3 1
1 2 3
"""

def main():
    import io
    f = io.StringIO(inp)
    ntcase = int(next(f).strip())
    for i in range(ntcase):
        N, K = (int(x) for x in next(f).strip().split())
        L = [int(x) for x in next(f).strip().split()]
        assert(len(L) == N)
        print(solve(L, K))

if __name__ == '__main__':
    main()

(Apr-09-2022, 07:15 AM)Gribouillis Wrote: I think the problem in the algorithm is that if a value val is the maximum of a subarray and this value is reached more than once in the subarray, your algorithm counts the subarray once for each of these values. You could perhaps correct this by replacing a[j] <= val with a[j] < val at line 23 in the last «while» loop. This would count the subarray only if val is the last instance of this value in the subarray.