Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())

A = list(map(int,input().split()))

dic = {}

for i in A:

    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

lis = []

for i in dic:

    lis.append(dic[i])

lis.sort()

ans = 0

"""
num = len(lis) - K
if num < 0:
    num = 0

for i in range(num):
    ans += lis[i]
"""
lo = len(lis)

while lo > K:
 
    ans += lis[0]
    del lis[0]
    lo = len(lis)

print (ans)


Fixed submission:

N,K = map(int,input().split())

A = list(map(int,input().split()))

dic = {}

for i in A:

    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

lis = []

for i in dic:

    lis.append(dic[i])

lis.sort()

ans = 0

num = len(lis) - K
if num < 0:
    num = 0

for i in range(num):
    ans += lis[i]

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())

A = list(map(int,input().split()))

dic = {}

for i in A:

    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

lis = []

for i in dic:

    lis.append(dic[i])

lis.sort()

ans = 0

cnt = 0
while len(lis) > K:

    ans += lis[0]
    del lis[0]

    cnt += 1
    if cnt > 200000:
        break

print (ans)


Fixed submission:

N,K = map(int,input().split())

A = list(map(int,input().split()))

dic = {}

for i in A:

    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

lis = []

for i in dic:

    lis.append(dic[i])

lis.sort()

ans = 0

num = len(lis) - K
if num < 0:
    num = 0

for i in range(num):
    ans += lis[i]

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())

A = list(map(int,input().split()))

dic = {}

for i in A:

    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

lis = []

for i in dic:

    lis.append(dic[i])

lis.sort()

ans = 0

while len(lis) > K:

    ans += lis[0]
    del lis[0]

print (ans)


Fixed submission:

N,K = map(int,input().split())

A = list(map(int,input().split()))

dic = {}

for i in A:

    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

lis = []

for i in dic:

    lis.append(dic[i])

lis.sort()

ans = 0

num = len(lis) - K
if num < 0:
    num = 0

for i in range(num):
    ans += lis[i]

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):

"""

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_e

回文をちゃんと定義しよう？
左の文字を何回変化させたら右になるか、をxとする
iを並べた時、対象の部分の和は26(の倍数)でなくてはならない
ただし、xの列が奇数調なら真ん中は0

abba なら
1,0,25

すると、l,rは2点を更新するだけになる
index l-1を+1し、rを-1する(mod26せよ,1-origin)
左右反転した部分の和を配列yとしてもつ(mod26)
すると、配列の2つの部分に+1,-1する操作を好きな回数だけ行って全て
26の倍数にせよという問題になる。

+→-の有向グラフで考える
まず、連結成分ごとに全てのノードの初期値の総和が26の倍数で無いなら不可能
そうでなければ可能(端から合わせていけば絶対つじつまが合うため)
解けたのでは？
あ、ただし、-1 or len(S-1)とリンクしてる連結成分は26の倍数でなくてもよい
1-indexedのほうがいいか？
0 or len(S)とリンクしてる連結成分は26の倍数でなくてもよい

"""
import sys
sys.setrecursionlimit(200000)
alp = "abcdefghijklmnopqrstuvwxyz"
ad = {}
for i in range(26):
    ad[alp[i]] = i

S = input()
x = []

for i in range(len(S)-1):
    x.append((ad[S[i+1]]-ad[S[i]]) % 26)

y = [0]
for j in range((len(x)+1)//2):

    j2 = len(x)-1-j

    if j != j2:
        y.append(x[j]+x[j2])
    else:
        y.append(x[j])

#print (x,y)
N = int(input())

lis = [ [] for i in range(len(y)) ] #連結リスト
for loop in range(N):
    
    l,r = map(int,input().split())
    l -= 1

    l = min( l , len(x)+1-l )
    r = min( r , len(x)+1-r )

    lis[l].append(r)
    lis[r].append(l)

#print (lis)

def dfs(v):
    ret = y[v]
    visit[v] = True
    for nex in lis[v]:
        if not visit[nex]:
            ret += dfs(nex)
    return ret

visit = [False] * len(lis)
ans = "YES"
for i in range(len(lis)):

    if visit[i]:
        continue
    rec = dfs(i)
    if i != 0 and rec % 26 != 0:
        ans = "NO"
        break

print (ans)


Fixed submission:

"""

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_e

回文をちゃんと定義しよう？
左の文字を何回変化させたら右になるか、をxとする
iを並べた時、対象の部分の和は26(の倍数)でなくてはならない
ただし、xの列が奇数調なら真ん中は0

abba なら
1,0,25

すると、l,rは2点を更新するだけになる
index l-1を+1し、rを-1する(mod26せよ,1-origin)
左右反転した部分の和を配列yとしてもつ(mod26)
すると、配列の2つの部分に+1,-1する操作を好きな回数だけ行って全て
26の倍数にせよという問題になる。

+→-の有向グラフで考える
まず、連結成分ごとに全てのノードの初期値の総和が26の倍数で無いなら不可能
そうでなければ可能(端から合わせていけば絶対つじつまが合うため)
解けたのでは？
あ、ただし、-1 or len(S-1)とリンクしてる連結成分は26の倍数でなくてもよい
1-indexedのほうがいいか？
0 or len(S)とリンクしてる連結成分は26の倍数でなくてもよい

"""
import sys
sys.setrecursionlimit(200000)
alp = "abcdefghijklmnopqrstuvwxyz"
ad = {}
for i in range(26):
    ad[alp[i]] = i

S = input()
x = []

for i in range(len(S)-1):
    x.append((ad[S[i+1]]-ad[S[i]]) % 26)

y = [0]
for j in range((len(x)+1)//2):

    j2 = len(x)-1-j

    if j != j2:
        y.append(x[j]+x[j2])
    else:
        y.append(x[j])

#print (x,y)
N = int(input())

lis = [ [] for i in range(len(y)) ] #連結リスト
for loop in range(N):
    
    l,r = map(int,input().split())
    l -= 1

    l = min( l , len(x)+1-l )
    r = min( r , len(x)+1-r )

    lis[l].append(r)
    lis[r].append(l)

#print (lis)

def dfs(v):
    ret = y[v]
    visit[v] = True
    for nex in lis[v]:
        if not visit[nex]:
            ret += dfs(nex)
    return ret

visit = [False] * len(lis)
ans = "YES"
for i in range(len(lis)):

    if visit[i]:
        continue
    rec = dfs(i)
    if i != 0 and rec % 26 != 0:
        ans = "NO"
        break

print (ans)
Buggy python submission (verdict: Runtime Error):
flag=1

a=input()
b=input()

c=""
d=""

c[0]=b[2]
c[1]=b[1]
c[2]=b[0]

d[0]=a[2]
d[1]=a[1]
d[3]=a[0]

i=0

while i<3:
    if a[i]!=c[i]:
        flag=0
    i+=1

while j<3:
    if b[j]!=d[j]:
        flag=0
    j+=1

if flag=1:
    print("YES")
else:
    print("NO")

Fixed submission:

up = input()
down = input()

down_re = ""

for i in down:
    down_re = i + down_re
    
if up == down_re:
    print ("YES")
    
else:
    print ("NO")
Buggy python submission (verdict: Runtime Error):

N = int(input().split())

i = 0
while True:

    if i ** 2 > N:
        print ((i-1)**2)
        break

Fixed submission:

N = int(input())

i = 0
while True:

    if i ** 2 > N:
        print ((i-1)**2)
        break

    i += 1

Buggy python submission (verdict: Runtime Error):

N = input().split()

i = 0
while True:

    if i ** 2 > N:
        print ((i-1)**2)
        break

Fixed submission:

N = int(input())

i = 0
while True:

    if i ** 2 > N:
        print ((i-1)**2)
        break

    i += 1
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.sort()
B.sort()
C.sort()

ans = 0

for c in C:

    for b in B:

        if b >= c:
            break

        for a in A:

            if a >= b:
                break

            else:

                ans += 1

print (ans)


Fixed submission:

N = int(input())

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

A.sort()
B.sort()
C.sort()

A.append(10 ** 9 + 2)

ap = 0

Bnum = []

ans = 0

for i in range(N):

    b = B[i]

    while True:

        if A[ap] < b:

            ap += 1

        else:

            break

    if i == 0:
        Bnum.append(ap)

    else:
        Bnum.append(ap + Bnum[-1])

bp = 0
B.append(10 ** 9 + 2)

for i in range(N):

    c = C[i]

    while True:

        if B[bp] < c:

            bp += 1

        else:

            break

    if bp != 0:
        ans += Bnum[bp-1]

print (ans)
Buggy python submission (verdict: Runtime Error):
import sys

s = input()

rem = []
remrev = []

for i in s:
    if i != "x":
        rem.append(i)
        remrev.append(i)

remrev.reverse()

for i in range(len(rem)):

    if rem[i] != remrev[i]:
        print (-1)
        sys.exit()

nx = 0
xnum = []

for i in s:

    if i == "x":
        nx += 1
    else:
        xnum.append(nx)
        nx = 0

xnum.append(nx)

xnc = xnum.copy()
xnc.reverse()

ans = 0

for i in range((len(xnum) + 1) // 2):

    ans += abs(xnum[i]-xnc[i])

print (ans)

Fixed submission:
import sys

s = input()

rem = []
remrev = []

for i in s:
    if i != "x":
        rem.append(i)
        remrev.append(i)

remrev.reverse()

for i in range(len(rem)):

    if rem[i] != remrev[i]:
        print (-1)
        sys.exit()

nx = 0
xnum = []

for i in s:

    if i == "x":
        nx += 1
    else:
        xnum.append(nx)
        nx = 0

xnum.append(nx)

xnc = xnum.copy()
xnc.reverse()

ans = 0

for i in range((len(xnum) + 1) // 2):

    ans += abs(xnum[i]-xnc[i])

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):

A,B,C,D,E,F = map(int,input().split())

amax = F // (100 * A)
bmax = F // (100 * B)
cmax = F // C
dmax = F // D

ans = 0
summ = 0
suge = 0


for a in range(amax+1):

    for b in range(bmax+1):

        for c in range(cmax+1):

            for d in range(dmax+1):


                if 100*A*a + 100*B*b + C*c + D*d <= F and (A*100*a+B*100*b)*E >= 100*(C*c+D*d):

                    if A*100*a+B*100*b+C*c+D*d !=0 and ans < 100*(C*c+D*d)/(A*100*a+B*100*b+C*c+D*d):

                        ans = 100*(C*c+D*d)/(A*100*a+B*100*b+C*c+D*d)
                        summ = A*100*a+B*100*b+C*c+D*d
                        suge = C*c+D*d

if summ == 0:
    summ = 100*A
print (summ,suge)

Fixed submission:

A,B,C,D,E,F = map(int,input().split())

amax = F // (100 * A)
bmax = F // (100 * B)
cmax = F // C
dmax = F // D

ans = 0
summ = 0
suge = 0


for a in range(amax+1):

    for b in range(bmax+1):

        for c in range(cmax+1):

            for d in range(dmax+1):


                if 100*A*a + 100*B*b + C*c + D*d <= F and (A*100*a+B*100*b)*E >= 100*(C*c+D*d):

                    if A*100*a+B*100*b+C*c+D*d !=0 and ans < 100*(C*c+D*d)/(A*100*a+B*100*b+C*c+D*d):

                        ans = 100*(C*c+D*d)/(A*100*a+B*100*b+C*c+D*d)
                        summ = A*100*a+B*100*b+C*c+D*d
                        suge = C*c+D*d

if summ == 0:
    summ = 100*A
print (summ,suge)
Buggy python submission (verdict: Time Limit Exceeded):



def wantans(nowp,sc,rlis,ans):

    if len(rlis) == 0:
        ans = min(ans , sc)
        return ans

    for i in range(len(rlis)):

        nexsc = sc
        nexlis = rlis.copy()
        del nexlis[i]

        if nowp != None:
            nexsc += lis[nowp][rlis[i]]
            
        ans = wantans(rlis[i],nexsc,nexlis,ans)

    return ans
        




N,M,R = map(int,input().split())

r = list(map(int,input().split()))

lis = [ [float("inf")] * N for i in range(N) ]

for i in range(N):

    lis[i][i] = 0

for i in range(M):

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

    A -= 1
    B -= 1

    lis[A][B] = C
    lis[B][A] = C

for k in range(N):

    for i in range(N):

        for j in range(N):

            lis[i][j] = min(lis[i][j],lis[i][k]+lis[k][j])



for i in range(R):
    r[i] -= 1
    
ans = wantans(None,0,r,float("inf"))

print (ans)


Fixed submission:



def wantans(nowp,sc,rlis,ans):

    if len(rlis) == 0:
        ans = min(ans , sc)
        return ans

    for i in range(len(rlis)):

        nexsc = sc

        nexlis = []
        for j in range(len(rlis)):
            if i != j:
                nexlis.append(rlis[j])

        if nowp != None:
            nexsc += lis[nowp][rlis[i]]
            
        ans = wantans(rlis[i],nexsc,nexlis,ans)

    return ans
        




N,M,R = map(int,input().split())

r = list(map(int,input().split()))

lis = [ [float("inf")] * N for i in range(N) ]

for i in range(N):

    lis[i][i] = 0

for i in range(M):

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

    A -= 1
    B -= 1

    lis[A][B] = C
    lis[B][A] = C

for k in range(N):

    for i in range(N):

        for j in range(N):

            lis[i][j] = min(lis[i][j],lis[i][k]+lis[k][j])



for i in range(R):
    r[i] -= 1
    
ans = wantans(None,0,r,float("inf"))

print (ans)
Buggy python submission (verdict: Runtime Error):
from decimal import Decimal
import fractions


N = int(input())

now = Decimal("1")

for i in range(N):

    T = Decimal(input())

    now = now * T / fractions.gcd(now,T)

print("{:.0f}".format(now))


Fixed submission:
import fractions

N = int(input())

now = 1

for i in range(N):

    T = int(input())

    now = now * T // fractions.gcd(now , T)

print (now)

Buggy python submission (verdict: Runtime Error):
from decimal import Decimal
import fractions


N = int(input())

now = Decimal("1")

for i in range(N):

    T = Decimal(input())

    now = now * T / fractions.gcd(now,T)

now = int(now)

print("{:.100g}".format(now))


Fixed submission:
import fractions

N = int(input())

now = 1

for i in range(N):

    T = int(input())

    now = now * T // fractions.gcd(now , T)

print (now)
Buggy python submission (verdict: Runtime Error):
from collections import deque

N = int(input())

abc = []

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    if a not in dic:
        dic[a-1] = []
    if b not in dic:
        dic[b-1] = []

    dic[a-1].append([b-1,c])
    dic[b-1].append([a-1,c])

Q,K = map(int,input().split())

K -= 1

lis = [0] * N

queue = deque([])

queue.append(K)

while len(queue) > 0:

    now = queue.pop()

    for nlis in dic[now]:

        if lis[nlis[0]] != 0 or nlis[0] == K:
            continue

        lis[nlis[0]] = lis[now] + nlis[1]
        queue.append(nlis[0])

#print (lis)

for i in range(Q):

    x,y = map(int,input().split())

    print (lis[x-1]+lis[y-1])

        


Fixed submission:
from collections import deque

N = int(input())

depth = [""] * N

lis = [0] * N

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append([b,c])
    dic[b].append([a,c])

Q,K = map(int,input().split())
K -= 1

queue = deque([])
queue.append(K)
depth[K] = 0

while len(queue) > 0:

    now = queue.pop()

    if now not in dic:
        continue

    for bc in dic[now]:

        b = bc[0]
        c = bc[1]
        
        if depth[b] != "":
            continue

        depth[b] = depth[now] + 1
        lis[b] = lis[now] + c
        queue.append(b)

for i in range(Q):

    x,y = map(int,input().split())

    x -= 1
    y -= 1

    print (lis[x] + lis[y])
Buggy python submission (verdict: Time Limit Exceeded):

N,M = map(int,input().split())

slink = []
glink = []

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink.append(b)
    elif b == 1:
        slink.append(a)
    elif a == N:
        glink.append(b)
    elif b == N:
        glink.append(a)

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

print (ans)

Fixed submission:

N,M = map(int,input().split())

slink = {}
glink = {}

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink[b] = 1
    elif b == 1:
        slink[a] = 1
    elif a == N:
        glink[b] = 1
    elif b == N:
        glink[a] = 1

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):

N,M = map(int,input().split())

slink = []
glink = []

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink.append(b)
    elif b == 1:
        slink.append(a)
    elif a == N:
        glink.append(b)
    elif b == N:
        glink.append(a)

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"

print (ans)

Fixed submission:

N,M = map(int,input().split())

slink = {}
glink = {}

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink[b] = 1
    elif b == 1:
        slink[a] = 1
    elif a == N:
        glink[b] = 1
    elif b == N:
        glink[a] = 1

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

print (ans)
Buggy python submission (verdict: Runtime Error):
import fractions

N,K = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

for i in range(N-1):

    if i == 0:
        now = fractions.gcd(A[0],A[1])

    else:
        now = fractions.gcd(now,A[i+1])

if K % now == 0 and K <= A[-1]:
    print ("POSSIBLE")
else:
    print ("IMPOSSIBLE")


Fixed submission:
import fractions
import sys

N,K = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

if len(A) == 1:
    if A[0] == K:
        print ("POSSIBLE")
    else:
        print ("IMPOSSIBLE")
    sys.exit()

for i in range(N-1):

    if i == 0:
        now = fractions.gcd(A[0],A[1])

    else:
        now = fractions.gcd(now,A[i+1])

if K % now == 0 and K <= A[-1]:
    print ("POSSIBLE")
else:
    print ("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):

N,M,D = map(int,input().split())

A = list(map(int,input().split()))


lis = [i for i in range(N)]

for i in range(M):

    a = A[i] - 1

    k = lis[a]
    lis[a] = lis[a+1]
    lis[a+1] = k


#print (lis)

end = [False] * N
endp = 0
ans = [None] * N

while endp < N:

    if end[endp]:
        endp += 1

    else:
        q = []
        start = endp
        now = endp

        while len(q) == 0 or start != now:

            q.append(now)
            now = lis[now]

        amari = D % len(q)

        for i in range(len(q)):

            end[q[i]] = True
            ind = (i + amari) % len(q)
            ans[q[i]] = q[ind]

ans2 = [0] * N

for i in range(N):

    ans2[ans[i]] = i + 1

for i in ans2:
    print (i)


Fixed submission:

import sys

N,A,B,C,D = map(int,input().split())
num = abs(A-B)
nmax = (N-1) * D
nmin = (N-1) * C
flag = False

for i in range(N-1):

    if nmax >= num and num >= nmin:
        flag = True
        break

    nmax -= D + C
    nmin -= C + D

if flag:
    print ("YES")
else:
    print ("NO")
Buggy python submission (verdict: Runtime Error):

n = int(input())

a = list(map(int,input().split()))

indlis = [-1] * (n+1)


for i in range(n):

    if indlis[a[i]] == -1:
        indlis[a[i]] = i

    else:
        L = indlis[a[i]]
        R = i
        break

#print (L,R)
nall = n+1
nsub = 1

for i in range(n+1):

    print ((nall - nsub) % (10 ** 9 + 7))

    nall *= n - i
    nall //= 2+i

    nsub *= n-R+L-i
    nsub //= 1+i


Fixed submission:
#modの掛け算

def modmal(a,b,mod): #a*bをmodを法にして求める

    return a * b % mod


#modの割り算

def moddiv(a,b,mod): #a/bをmodを法にして求める

    return (a * pow(b,mod-2,mod)) % mod


#逆元

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


n = int(input())

dic = {}

a = list(map(int,input().split()))
twonum = None

for i in range(n+1):

    if a[i] not in dic:
        dic[a[i]] = [i]
    else:
        dic[a[i]].append(i)
        twonum = a[i]

mod = 10**9+7
fac,inv = modfac(n+10,mod)

for k in range(n+1):
    
    k += 1
    
    ans = modnCr(n+1,k,mod,fac,inv)

    l = dic[twonum][0]
    r = (n+1) - dic[twonum][1] - 1

    if l+r >= k-1:
        ans -= modnCr(l+r,k-1,mod,fac,inv)

    print (ans % mod)
Buggy python submission (verdict: Runtime Error):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

a = list(map(int,input().split()))

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    if a[i+1] == (a[i]+1)%m:
        continue

    start[a[i] % m].append(i)
    end[(a[i+1]-1) % m].append(i)

    allsum += (a[i+1]-a[i]) % m


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

if (allsum - max(lis) < 0):
    print (asxacscd)
print (allsum - max(lis))

Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    allsum += (a[i+1]-a[i]) % m
    if a[i+1] == (a[i]+1)%m:
        continue

    start[(a[i]+1) % m].append(i)
    end[a[i+1] % m].append(i)

    


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

if (allsum - max(lis) < 0):
    print (asxacscd)
#print (lis)
print (allsum - max(lis))
Buggy python submission (verdict: Runtime Error):

def bitadd(a,w,bit): #aにwを加える(1-origin)

    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)

def bitsum(a,bit): #ind 0～aまでの和を求める

    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


N,K = map(int,input().split())

a = []

for i in range(N):

    A = int(input())
    a.append(A-K)


B = [0]

for i in range(N):

    B.append(B[-1] + a[i])

#print (B)
C = B.copy()
C.sort()

dic = {}

num = 1
for i in range(N+1):

    if i == 0:
        dic[C[i]] = num
        num += 1
    elif C[i] != C[i-1]:
        dic[C[i]] = num
        num += 1

for i in range(N+1):
    B[i] = dic[B[i]]

BIT = [0] * (len(B) + 1)

ans = 0

for i in range(N+1):

    ans += bitsum(B[i],BIT)
    bitadd(B[i],1,BIT)

print (ans)
    


Fixed submission:

def bitadd(a,w,bit): #aにwを加える(1-origin)

    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)

def bitsum(a,bit): #ind 0～aまでの和を求める

    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


N,K = map(int,input().split())

a = []

for i in range(N):

    A = int(input())
    a.append(A-K)


B = [0]

for i in range(N):

    B.append(B[-1] + a[i])

#print (B)
C = B.copy()
C.sort()

dic = {}

num = 1
for i in range(N+1):

    if i == 0:
        dic[C[i]] = num
        num += 1
    elif C[i] != C[i-1]:
        dic[C[i]] = num
        num += 1

for i in range(N+1):
    B[i] = dic[B[i]]

BIT = [0] * (len(B) + 1)

ans = 0

for i in range(N+1):

    ans += bitsum(B[i],BIT)
    bitadd(B[i],1,BIT)

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())

now = 0
lis = []

for i in range(N):

    a,b = map(int,input().split())
    lis += [a]*b



lis.sort()
print (lis[K-1])


Fixed submission:

N,K = map(int,input().split())

now = 0
dic = {}
lis = []

for i in range(N):

    a,b = map(int,input().split())

    if a in dic:
        dic[a] += b
    else:
        dic[a] = b
        lis.append(a)

lis.sort()

for i in lis:

    now += dic[i]

    if now >= K:
        print (i)
        break