Submission #5300115

---

Source Code Expand

import sys
from collections import Counter
sys.setrecursionlimit(10**6)
N, X = map(int, input().split())
A = list(map(int, input().split()))
def count(B):
    L = len(B)
    if L == 1:
        return 0
    B1 = (B[:L//2])[::-1]
    B2 = B[L//2:]
    res = 0
    M1 = [0]*(L//2)
    M2 = [0]*(-(-L//2))
    C1 = [0]*(L//2)
    C2 = [0]*(-(-L//2))
    maxi = -1
    cnt = 0
    for i, b in enumerate(B1):
        if b == maxi:
            cnt += 1
        elif b > maxi:
            maxi = b
            cnt = 1
        M1[i] = maxi
        C1[i] = cnt
    maxi = -1
    cnt = 0
    for i, b in enumerate(B2):
        if b == maxi:
            cnt += 1
        elif b > maxi:
            maxi = b
            cnt = 1
        M2[i] = maxi
        C2[i] = cnt
    e2 = -1
    table = Counter()
    for b, m, c in zip(B1, M1, C1):
        while e2 < -(-L//2) - 1 and B2[e2+1] <= b:
            e2 += 1
            table[B2[e2]] += 1
        if 0 <= X - b - m <= 10**5:
            res += table[X - b - m]*c
    e1 = -1
    table = Counter()
    for b, m, c in zip(B2, M2, C2):
        while e1 < L//2 - 1 and B1[e1+1] <= b:
            e1 += 1
            table[B1[e1]] += 1
        if 0 <= X - b - m <= 10**5:
            res += table[X - b - m]*c
    return res
J = []
def div(C):
    L = len(C)
    if L == 1:
        return
    J.append(C)
    div(C[:L//2])
    div(C[L//2:])
div(A)
ans = 0
if not X % 3:
    ans += A.count(X//3)
for j in J:
    ans += count(j)
print(ans)

Submission Info

Judge Result