Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def seachPrimeNum(N):
  max = int(np.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

n=10**5
a=seachPrimeNum(n)
b=[]
y=0
x=0
while x<=100000:
  t=a[y]
  x=t*2-1
  b.append(x)
  y+=1
  
c=set(a)&set(b)

q=int(input())
for p in range(q):
  ans=0
  w,z=map(int,input().split())
  for j in c:
    if w<=j<=z:
      ans+=1
    if j<w or z<j:
      continue
  print(ans)



Fixed submission:
import numpy as np
def seachPrimeNum(N):
  max = int(np.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

n=10**5
a=seachPrimeNum(n)
b=[]
y=0
x=0
while x<=100000:
  t=a[y]
  x=t*2-1
  b.append(x)
  y+=1
  
c=set(a)&set(b)

q=int(input())
r=[0 for _ in range(100000)]
for f in c:
  r[f]=1
for g in range(len(r)-1):
  r[g+1]=r[g]+r[g+1]

for p in range(q):
  w,z=map(int,input().split())
  print(r[z]-r[w-1])
Buggy python submission (verdict: Runtime Error):
s=input()
print(s.count('1')

Fixed submission:
s=input()
print(s.count('1'))
Buggy python submission (verdict: Runtime Error):
s=input()
ans=[]

for i in range(2**3):
  a=int(s[0])
  for j in range(3):
    if ((i>>j)&1):
      a+=int(s[j+1])
    elif ((i>>j)&0):
      a-=int(s[j+1])
      
  if a==7:
    ans.append(i)
    
u=ans[0]
ans1=[]
for j in range(3):
  if ((i>>j)&1):
      ans1.append('+')
  elif ((i>>j)&0):
      ans1.append('-')
      
print(s[0]+ans1[0]+s[1]+ans1[1]+s[2]+ans1[2]+s[3]+'=7')
    

Fixed submission:
s=input()
ans=[]

for i in range(2**3):
  a=int(s[0])
  for j in range(3):
    if ((i>>j)&1):
      a+=int(s[j+1])
    else:
      a-=int(s[j+1])
      
  if a==7:
    ans.append(i)
    
u=ans[0]
ans1=[]
for j in range(3):
  if ((u>>j)&1):
      ans1.append('+')
  else:
      ans1.append('-')
      
print(s[0]+ans1[0]+s[1]+ans1[1]+s[2]+ans1[2]+s[3]+'=7')

Buggy python submission (verdict: Runtime Error):
s=input()
ans=[]

for i in range(2**3):
  a=int(s[0])
  for j in range(3):
    if ((i>>j)&1):
      a+=int(s[j+1])
    elif ((i>>j)&0):
      a-=int(s[j+1])
      
  if a==7:
    ans.append(i)
    
u=ans[0]
ans1=[]
for j in range(3):
  if ((i>>j)&1):
      ans1.append('+')
  else:
      ans1.append('-')
      
print(s[0]+ans1[0]+s[1]+ans1[1]+s[2]+ans1[2]+s[3]+'=7')
    

Fixed submission:
s=input()
ans=[]

for i in range(2**3):
  a=int(s[0])
  for j in range(3):
    if ((i>>j)&1):
      a+=int(s[j+1])
    else:
      a-=int(s[j+1])
      
  if a==7:
    ans.append(i)
    
u=ans[0]
ans1=[]
for j in range(3):
  if ((u>>j)&1):
      ans1.append('+')
  else:
      ans1.append('-')
      
print(s[0]+ans1[0]+s[1]+ans1[1]+s[2]+ans1[2]+s[3]+'=7')
Buggy python submission (verdict: Runtime Error):
a,b=map(input().split())
print('<' if a<b else '>' a>b else '=')

Fixed submission:
a,b=input().split()
print('<' if a<b else '>' if a>b else '=')
Buggy python submission (verdict: Runtime Error):
def bs_left(list, target):
    low = 0
    high = len(list)

    while low < high:
        mid = (low + high) // 2
        if target > list[mid]:
            low = mid + 1
        else:
            high = mid
    return low

def bs_right(list, target):
    low = 0
    high = len(list)
    while low < high:
        mid = (low + high) // 2
        if target < list[mid]:
            high = mid
        else:
            low = mid + 1
    return low

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    ans += (bs_left(A, b) * (n - bs_right(C, b)))
print(ans)



Fixed submission:
a=input()
b=input()
print('YES' if a[0]==b[2] and a[1]==b[1] and a[2]==b[0] else 'NO')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a=sorted(a)
b=sorted(b)
c=sorted(c)
c.reverse()

ans=0
max1=n-1

for x in range(n):
  maxC=c[x]
  min1=0
  while max1-min1>1:
    zantei=(max1+min1)//2
    if b[zantei]>=maxC:
      max1=zantei
    else:
      min1=zantei
  if b[max1]<maxC:
    ch=max1
  elif b[min1]>=maxC:
    continue
  else:
    
    ch=min1
  
  for y in range(ch+1):
    maxB=b[y]
    max2=n-1
    min2=0
    while max2-min2>1:
      zantei1=(max2+min2)//2
      if a[zantei1]>=maxB:
        max2=zantei1
      else:
        min2=zantei1
    if a[max2]<maxB:
      ch1=max2
    else:
      ch1=min2
      
    ans+=ch1+1
    
print(ans)
      

Fixed submission:
def bs_left(list, target):
    low = 0
    high = len(list)

    while low < high:
        mid = (low + high) // 2
        if target > list[mid]:
            low = mid + 1
        else:
            high = mid
    return low

def bs_right(list, target):
    low = 0
    high = len(list)
    while low < high:
        mid = (low + high) // 2
        if target < list[mid]:
            high = mid
        else:
            low = mid + 1
    return low

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    ans += (bs_left(A, b) * (n - bs_right(C, b)))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a=sorted(a)
b=sorted(b)
c=sorted(c)

ans=0

for x in range(n):
  maxC=c[x]
  min1=0
  max1=n-1
  while max1-min1>1:
    zantei=(max1+min1)//2
    if b[zantei]>=maxC:
      max1=zantei
    else:
      min1=zantei
  if b[max1]<maxC:
    ch=max1
  elif b[min1]>=maxC:
    continue
  else:
    
    ch=min1
  
  for y in range(ch+1):
    maxB=b[y]
    max2=n-1
    min2=0
    while max2-min2>1:
      zantei1=(max2+min2)//2
      if a[zantei1]>=maxB:
        max2=zantei1
      else:
        min2=zantei1
    if a[max2]<maxB:
      ch1=max2
    else:
      ch1=min2
      
    ans+=ch1+1
    
print(ans)

Fixed submission:
def bs_left(list, target):
    low = 0
    high = len(list)

    while low < high:
        mid = (low + high) // 2
        if target > list[mid]:
            low = mid + 1
        else:
            high = mid
    return low

def bs_right(list, target):
    low = 0
    high = len(list)
    while low < high:
        mid = (low + high) // 2
        if target < list[mid]:
            high = mid
        else:
            low = mid + 1
    return low

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    ans += (bs_left(A, b) * (n - bs_right(C, b)))
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

n=int(input())
ans=int(input())

if n>1:
  
  for x in range(n-1):
    s=int(input())
    ans=int(ans*s/(math.gcd(ans,s)))
    
  
print(ans)

Fixed submission:
import math

n=int(input())
ans=int(input())

if n>1:
  
  for x in range(n-1):
    s=int(input())
    ans=ans*s//(math.gcd(ans,s))
    
  
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

x2=0
x4=0
x1=0
for x in a:
  if x%2==0:
    x2+=1
  if x%4==0:
    x4+=1
  if x%2==1:
    x1+=1
    
if x4+x1==n:
  if x4>=x1-1:
    print('Yes')
  else:
    print('No')
  
else:
  if x4>=x1:
    print('Yes')
  else:
    
    print('No')


Fixed submission:
n,m=map(int,input().split())
print((m-1)*(n-1))
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input.split())

if c>a:
  print('YES')
else:
  print('NO')

Fixed submission:
a,b,c=map(int,input().split())
ch=0
for x in range(b):
  if (x*a)%b==c:
    ch+=1
    
if ch>0:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
a,b,c=import().split()
print(a[0].upper()+b[0].upper()+c[0].upper())

Fixed submission:
a,b,c=input().split()
print(a[0].upper()+b[0].upper()+c[0].upper())
Buggy python submission (verdict: Runtime Error):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = input().rstrip('\n')

    M = X.count("1")
    x_major = 0
    x_minor = 0
    for i in range(N):
        add = int(X[i])
        x_major = (x_major * 2 + add)%(M+1)
        x_minor = (x_minor * 2 + add)%(M-1)
    for i in range(N):
        if X[i] == "1":
            val = (x_minor - pow(2, N-i-1, M-1)) % (M-1)
        else:
            val = (x_major + pow(2, N-i-1, M+1)) % (M + 1)
        cnt = 1
        while val:
            val = val % bin(val).count("1")
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()


Fixed submission:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = input().rstrip('\n')

    M = X.count("1")
    flg = 0
    if M == 1:
        flg = 1
    x_major = 0
    x_minor = 0
    for i in range(N):
        add = int(X[i])
        x_major = (x_major * 2 + add)%(M+1)
        if flg == 0:
            x_minor = (x_minor * 2 + add)%(M-1)
    for i in range(N):
        if X[i] == "1":
            if flg:
                print(0)
                continue
            val = (x_minor - pow(2, N-i-1, M-1)) % (M-1)
        else:
            val = (x_major + pow(2, N-i-1, M+1)) % (M + 1)
        cnt = 1
        while val:
            val = val % bin(val).count("1")
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    D = int(input())
    C = list(map(int, input().split()))
    S = []
    for _ in range(D):
        S.append(list(map(int, input().split())))
    ans = 0
    last = [-1] * 26
    days = [[-1] for _ in range(26)]
    T = []
    for d in range(D):
        t = int(input()) - 1
        T.append(t)
        ans += S[d][t]
        last[t] = d
        days[t].append(d)
        for i in range(26):
            ans -= C[i] * (d - last[i])
    for t in range(26):
        days[t].append(D)

    M = int(input())
    for _ in range(M):
        d, q = map(int, input().split())
        d -= 1
        q -= 1
        t = T[d]
        ans += S[d][q]
        ans -= S[d][t]
        i = bisect_left(days[q], d)
        ans += C[q] * (d - days[q][i-1]) * (days[q][i] - d)
        j = bisect_left(days[t], d)
        ans -= C[t] * (d - days[t][i-1]) * (days[t][i+1] - d)
        #print(days[q], days[t])
        T[d] = q
        days[q].append(d)
        days[q].sort()
        days[t].remove(d)
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    D = int(input())
    C = list(map(int, input().split()))
    S = []
    for _ in range(D):
        S.append(list(map(int, input().split())))
    ans = 0
    last = [-1] * 26
    days = [[-1] for _ in range(26)]
    T = []
    for d in range(D):
        t = int(input()) - 1
        T.append(t)
        ans += S[d][t]
        last[t] = d
        days[t].append(d)
        for i in range(26):
            ans -= C[i] * (d - last[i])
    for t in range(26):
        days[t].append(D)

    M = int(input())
    for _ in range(M):
        d, q = map(int, input().split())
        d -= 1
        q -= 1
        t = T[d]
        ans += S[d][q]
        ans -= S[d][t]
        i = bisect_left(days[q], d)
        ans += C[q] * (d - days[q][i-1]) * (days[q][i] - d)
        j = bisect_left(days[t], d)
        ans -= C[t] * (d - days[t][j-1]) * (days[t][j+1] - d)
        #print(days[q], days[t])
        T[d] = q
        days[q].append(d)
        days[q].sort()
        days[t].remove(d)
        print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    M = 10**6

    A.sort()
    C = Counter(A)
    ans = 0
    seen = [0] * (M+1)
    for a in A:
        if C[a] == 1 and seen[a] == 0:
            ans += 1
        for j in range(1, M+1):
            if a * j > M:
                break
            seen[a*j] = 1
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    M = 10**6

    A.sort()
    C = Counter(A)
    ans = 0
    seen = [0] * (M+1)
    A = set(A)
    for a in A:
        if C[a] == 1 and seen[a] == 0:
            ans += 1
        for j in range(1, M+1):
            if a * j > M:
                break
            seen[a*j] = 1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    for _ in range(N):
        a, b = map(int, input().split())
        if a < 0:
            a = -a
            b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    zz = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == b == 0:
            zz += 1
            continue
        if a < 0:
            a = -a
            b = -b
        elif a == 0:
            if b < 0:
                b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print((ans + zz)%mod)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 6000
    BC = [1] * 6000
    AC = [1] * 6000
    for i in range(-lb, la+1):
        lab = min(la, lb)
        AB[i] = check(A[max(0, i):min(lab, i+lb)], B[max(0, -i):min(lab, lb-i)])
    for i in range(-lc, lb+1):
        lbc = min(lb, lc)
        BC[i] = check(B[max(0, i):min(lbc, i+lc)], C[max(0, -i):min(lbc, lc-i)])
    for i in range(-lc, la+1):
        lca = min(la, lc)
        AC[i] = check(A[max(0, i):min(lca, i+lc)], C[max(0, -i):min(lca, lc-i)])

    ans = la+lb+lc
    for i in range(-lb-lc, la+lc+1):
        if not AB[i]:
            continue
        for j in range(-lc, lb+1):
            if BC[j] and AC[i+j]:
                l = min(0, i, i+j)
                r = max(la, lb+i, lc+i+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 10010
    BC = [1] * 10010
    AC = [1] * 10010
    for i in range(-lb, la+1):
        AB[i] = check(A[max(0, i):min(la, i+lb)], B[max(0, -i):min(lb, la-i)])
    for i in range(-lc, lb+1):
        BC[i] = check(B[max(0, i):min(lb, i+lc)], C[max(0, -i):min(lc, lb-i)])
    for i in range(-lc, la+1):
        AC[i] = check(A[max(0, i):min(la, i+lc)], C[max(0, -i):min(lc, la-i)])

    ans = la+lb+lc
    for i in range(-lb-lc-3, la+lc+3):
        if not AB[i]:
            continue
        for j in range(-lb-lc-3, la+lb+3):
            if BC[j-i] and AC[j]:
                l = min(0, i, j)
                r = max(la, lb+i, lc+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        x, l = map(int, input().split())
        XL.append((x, l))
    XL.sort(key=lambda p: p[0] - p[1])

    inf = 10**10
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = -inf
    for i in range(N):
        x, l = XL[i]
        for j in range(N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j < N:
                if dp[i][j] <= x - l:
                    dp[i+1][j+1] = min(dp[i+1][j+1], x + l)
    for i in range(N, -1, -1):
        if dp[-1][i] < 10**10:
            print(i)
            exit()


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        x, l = map(int, input().split())
        XL.append((x, l))
    XL.sort(key=lambda p: p[1] + p[0])

    ans = 0
    prev = -10**10
    for i in range(N):
        x, l = XL[i]
        if x - l >= prev:
            ans += 1
            prev = x + l
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

mod = 10**9+7
N = int(input())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if not seen[u]:
            seen[u] = 1
            st.append(u)
            child[v].append(u)
seq.reverse()

ans = 0
half = pow(2, mod-2, mod)
half_n = pow(half, N-1, mod)
dp = [1] * (N+1)
for v in seq:
    tmp = (1 - half_n)%mod
    tmp2 = 0
    for u in child[v]:
        dp[v] += dp[u]
        tmp2 = (tmp2 + ((1 - pow(half, dp[u], mod))%mod * pow(half, N-dp[u]-1, mod)) % mod) % mod
    if dp[v] < N:
        tmp2 = (tmp2 + ((1 - pow(half, N-dp[v], mod)) % mod * pow(half, dp[v]-1, mod)) % mod) % mod
    if child[v]:
        tmp = (tmp - tmp2) % mod
        ans = (ans + tmp) % mod

print((ans * half)%mod)


Fixed submission:
import sys
input = sys.stdin.buffer.readline

mod = 10**9+7
N = int(input())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if not seen[u]:
            seen[u] = 1
            st.append(u)
            child[v].append(u)
seq.reverse()

ans = 0
half = pow(2, mod-2, mod)
half_n = pow(half, N-1, mod)
dp = [1] * (N+1)
for v in seq:
    tmp = (1 - half_n)%mod
    tmp2 = 0
    for u in child[v]:
        dp[v] += dp[u]
        tmp2 = (tmp2 + ((1 - pow(half, dp[u], mod))%mod * pow(half, N-dp[u]-1, mod)) % mod) % mod
    if dp[v] < N:
        tmp2 = (tmp2 + ((1 - pow(half, N-dp[v], mod)) % mod * pow(half, dp[v]-1, mod)) % mod) % mod
    if child[v]:
        tmp = (tmp - tmp2) % mod
        ans = (ans + tmp) % mod

print((ans * half)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

ok = N-1
ng = -1
mid = (ok+ng)//2
while ok - ng > 1:
    if mid >= N - P:
        ok = mid
        continue
    K = A[mid] + M
    if K < A[N - P]:
        ng = mid
        mid = (ok+ng)//2
        continue
    p = M * (V-P)
    flg = 0
    for i in range(mid):
        p -= M
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
        continue
    for i in range(mid+1, N - (P-1)):
        p -= K - A[i]
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
    else:
        ng = mid
        mid = (ok+ng)//2

print(N - ok)


Fixed submission:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

ok = N-1
ng = -1
mid = (ok+ng)//2
while ok - ng > 1:
    if mid >= N - P:
        ok = mid
        mid = (ok+ng)//2
        continue
    K = A[mid] + M
    if K < A[N - P]:
        ng = mid
        mid = (ok+ng)//2
        continue
    p = M * (V-P)
    flg = 0
    for i in range(mid):
        p -= M
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
        continue
    for i in range(mid+1, N - (P-1)):
        p -= K - A[i]
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
    else:
        ng = mid
        mid = (ok+ng)//2

print(N - ok)