Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = []
            res.extend(rule[j + 1])
    print(ans)


if __name__ == '__main__':
    main()


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


def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = rule[j + 1][:]
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
rule = [[] for _ in range(n)]
for i in range(m):
    rule[data[i][0] - 1].append(data[i][1])
    rule[data[i][1] - 1].append(data[i][0])
res = rule[0][:]
ans = 0
for j in range(n - 1):
    if j + 2 not in res:
        for k in range(len(rule[j + 1])):
            res.append(rule[j + 1][k])
    else:
        ans += 1
        res = []
        for k in range(len(rule[j + 1])):
            res.append(rule[j + 1][k])
print(ans)


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


def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = rule[j + 1][:]
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(n):
        if i < j:
            ans += a[i] * a[j]
            ans %= (10**9 + 7)


print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

ans = 0

a_goketi = sum(a)
b = []

for i in range(n):
    b.append(a_goketi - a[i])
    a_goketi -= a[i]

    ans += a[i] * b[i] 

ans %= 1000000007
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
arr = list(map(int, input().split()))

temp = arr.index(1)
ans = 1

while(temp!=0):
    val = arr[:temp].index(min(arr[:temp]))
    ans += 1
    temp = val
print(ans)


Fixed submission:
n = int(input())
arr = list(map(int, input().split()))

ind = [0]*(n+1)
for i in range(n):
    ind[arr[i]] = i
temp = 100000000
ans = 0
for i in range(1,n+1):
    if ind[i]<temp:
        ans+=1
        temp = ind[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
print(r**2)

Fixed submission:
r = int(input())
print(r**2)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve(s, MAX):
    if s < 3:
        return 0
    elif s < 6:
        return 1
    
    res = 1
    s -= 3
    while s > 2:
        res += solve(s, MAX)
        res %= MAX
        s -= 1
    return res


MAX=10**9+7
s = int(input())
res = solve(s, MAX)
print(res)



Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve(s, MAX):
    if s < 3:
        return 0
    elif s < 6:
        return 1
    a = 1
    b = 1
    c = 1
    num = 6
    while num <= s:
        tmp = a
        a = b
        b = c
        c += tmp
        c %= MAX
        num += 1
    return c


MAX=10**9+7
s = int(input())
res = solve(s, MAX)

print(res)
Buggy python submission (verdict: Runtime Error):
# 問題：https://atcoder.jp/contests/abc176/tasks/abc176_d

import numpy as np

h, w = map(int, input().strip().split())
cx, cy = map(int, input().strip().split())
dx, dy = map(int, input().strip().split())
cx -= 1
cy -= 1
dx -= 1
dy -= 1
qx = [cx]
qy = [cy]

s = [input() for _ in range(h)]
reached = np.zeros((h, w))
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            reached[i].append(0)
        if s[i][j] == '#':
            reached[i].append(1)
res = 0

while qx:
    pre_qx = []
    pre_qy = []
    while qx:
        x = qx.pop(0)
        y = qy.pop(0)
        if reached[x][y] == 1:
            continue
        pre_qx.append(x)
        pre_qy.append(y)
        reached[x][y] = 1
        if x > 0 and reached[x-1][y] == 0:
            qx.append(x-1)
            qy.append(y)
        if x < h-1 and reached[x+1][y] == 0:
            qx.append(x+1)
            qy.append(y)
        if y > 0 and reached[x][y-1] == 0:
            qx.append(x)
            qy.append(y-1)
        if y < w-1 and reached[x][y+1] == 0:
            qx.append(x)
            qy.append(y+1)
    if reached[dx][dy] == 1:
        break
    res += 1
    while pre_qx:
        x = pre_qx.pop(0)
        y = pre_qy.pop(0)
        lx = max(x-2, 0)
        rx = min(x+3, h)
        ly = max(y-2, 0)
        ry = min(y+3, w)
        for i in range(lx, rx):
            for j in range(ly, ry):
                if reached[i][j] == 0:
                    qx.append(i)
                    qy.append(j)

if reached[dx][dy] == 0:
    res = -1

print(res)



Fixed submission:
# 問題：https://atcoder.jp/contests/abc176/tasks/abc176_a

n, x, t = map(int, input().strip().split())
res = (n-1) // x + 1
res *= t
print(res)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M, K = map(int, input().split())
result = 0 # max
a_time = list(map(int, input().split()))
b_time = list(map(int, input().split()))

sum = 0

a_num = 0
for i in range(N):
    sum += a_time[i]
    a_num += 1
    if sum > K:
        sum -= a_time[i]
        a_num -= 1
        break
i = a_num
while i >= 0:
    sum -= a_time[i]
    for j in range(M):
        sum += b_time[j]
        if sum > K:
            sum -= b_time[j]
            break
    if result < i + j:
        result = i + j
    i -= 1

print(result)


Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M, K = map(int, input().split())
result = 0 # max
a_time = list(map(int, input().split()))
b_time = list(map(int, input().split()))

sum = 0

a_num = 0
for i in range(N):
    sum += a_time[i]
    a_num += 1
    if sum > K:
        sum -= a_time[i]
        a_num -= 1
        break
i = a_num
j = 0
while i >= 0:
    while sum < K and j < M:
        sum += b_time[j]
        j += 1
    if sum > K:
        j -= 1
        sum -= b_time[j]
    if result < i + j:
        result = i + j
    i -= 1
    sum -= a_time[i]

print(result)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M, K = map(int, input().split())
result = 0 # max
a_time = list(map(int, input().split()))
b_time = list(map(int, input().split()))

sum = 0

a_num = 0
for i in range(N):
    sum += a_time[i]
    a_num += 1
    if sum > K:
        sum -= a_time[i]
        a_num -= 1
        break
i = a_num
while i >= 0:
    sum -= a_time[i]
    for j in range(M):
        sum += b_time[j]
        if sum > K:
            sum -= b_time[j]
            break
    print('result={} i={} j={}'.format(result, i, j))
    if result < i + j:
        result = i + j
    i -= 1

print(result)


Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M, K = map(int, input().split())
result = 0 # max
a_time = list(map(int, input().split()))
b_time = list(map(int, input().split()))

sum = 0

a_num = 0
for i in range(N):
    sum += a_time[i]
    a_num += 1
    if sum > K:
        sum -= a_time[i]
        a_num -= 1
        break
i = a_num
j = 0
while i >= 0:
    while sum < K and j < M:
        sum += b_time[j]
        j += 1
    if sum > K:
        j -= 1
        sum -= b_time[j]
    if result < i + j:
        result = i + j
    i -= 1
    sum -= a_time[i]

print(result)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
for i in range(N):
    for j in range(i):
        if A[i-j-1] > A[i-j]:
            tmp = A[i-j]
            A[i-j] = A[i-j-1]
            A[i-j-1] = tmp
        print(A)

for i in range(K):
    result += A[i]

print(result)



Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
for i in range(N):
    for j in range(i):
        if A[i-j-1] > A[i-j]:
            tmp = A[i-j]
            A[i-j] = A[i-j-1]
            A[i-j-1] = tmp

for i in range(K):
    result += A[i]

print(result)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc127/tasks/abc127_d
# プライオリティキュー　解説を見ながら実装


import heapq

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

a = list(map(int, input().strip().split()))
a = list(map(lambda x: x*(-1), a))
for _ in range(m):
    b, c = map(int, input().strip().split())
    for _ in range(b):
        a.append(c * (-1))

heapq.heapify(a)
res = 0
for _ in range(n):
    res += heapq.heappop(a) * (-1)

print(res)


Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc127/tasks/abc127_d
# プライオリティキュー　解説を見ながら実装


import heapq

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

q = []
a = list(map(int, input().strip().split()))
for i in range(n):
    heapq.heappush(q,(a[i]*(-1), 1))
for i in range(m):
    b, c = map(int, input().strip().split())
    heapq.heappush(q,(c*(-1), b))

res = 0
for _ in range(n):
    c, b = heapq.heappop(q)
    res += c * (-1)
    if b > 1:
        b -= 1
        heapq.heappush(q, (c, b))

print(res)
Buggy python submission (verdict: Runtime Error):
3 2
2 1

Fixed submission:
H, W = map(int, input().strip().split())
h, w = map(int, input().strip().split())

res = (H - h) * (W - w)
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ans = 1
v = []
v = [int(x) for x in input().split()]
for x in v:
	ans = ans*x
if ans > 1e18:
	print(-1)
else :
	print(ans)

Fixed submission:
n = int(input())
ans = 1
v = []
v = [int(x) for x in input().split()]
v.sort()
for x in v:
	ans = ans*x
	if ans > 1e18:
		break
if ans > 1e18:
	print(-1)
else :
	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

mod = 10**9+7

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] * A[j]
        ans = ans % mod
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

mod = 10**9+7

sums = []
current_sum = 0
for a in A[1:][::-1]:
    current_sum += a
    sums.append(current_sum)
sums = sums[::-1]

ans = 0
for a, b in zip(A[:-1], sums):
    ans += a * b
    ans = ans % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

mod = 10**9+7

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans += A[i] * A[j]
print(ans % mod)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

mod = 10**9+7

sums = []
current_sum = 0
for a in A[1:][::-1]:
    current_sum += a
    sums.append(current_sum)
sums = sums[::-1]

ans = 0
for a, b in zip(A[:-1], sums):
    ans += a * b
    ans = ans % mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

if K % 2 == 0:
    print(-1)
else:
    n = 7
    i = 1
    while 1:
        if n % K == 0:
            break
        n = (n * 10 + 7) % K
        i += 1
    print(i)

Fixed submission:
K = int(input())

cycle = set()
if K % 2 == 0:
    print(-1)
else:
    n = 7
    i = 1
    while 1:
        if n in cycle:
            i = -1
            break
        if n % K == 0:
            break
        cycle.add(n)
        n = (n * 10 + 7) % K
        i += 1
       
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

if K % 2 == 0:
    print(-1)
else:
    n = 7
    i = 1
    while 1:
        if n % K == 0:
            break
        n = (n * 10 + 7) % K
        i += 1
    print(i)

Fixed submission:
K = int(input())

cycle = set()
if K % 2 == 0:
    print(-1)
else:
    n = 7
    i = 1
    while 1:
        if n in cycle:
            i = -1
            break
        if n % K == 0:
            break
        cycle.add(n)
        n = (n * 10 + 7) % K
        i += 1
       
    print(i)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

c = Counter(S)
S_target = 'R' * c['R'] + 'W' * c['W']

ans = 0
for a, b in zip(S, S_target):
    if b == 'W':
        break
    if a != b:
        ans += 1
print(ans)


Fixed submission:
from collections import Counter

N = int(input())
S = input()

c = Counter(S)
S_target = 'R' * c['R'] + 'W' * c['W']

ans = 0
for a, b in zip(S, S_target):
    if b == 'W':
        break
    if a != b:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

class Levenshtein:

    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance

    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)

N = int(input())
S = input()

c = Counter(S)
S_target = 'R' * c['R'] + 'W' * c['W']

leven = Levenshtein(S, S_target)
print(leven.dist // 2)

Fixed submission:
from collections import Counter

N = int(input())
S = input()

c = Counter(S)
S_target = 'R' * c['R'] + 'W' * c['W']

ans = 0
for a, b in zip(S, S_target):
    if b == 'W':
        break
    if a != b:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a_i = 0
b_i = 0
t = 0
count = 0
while t <= K:
    if a_i < len(A) and A[a_i] < B[b_i] and t + A[a_i] <= K:
        t += A[a_i]
        count += 1
        a_i += 1
    elif b_i < len(B) and t + B[b_i] <= K:
        t += B[b_i]
        count += 1
        b_i += 1
    else:
        break
print(count)

Fixed submission:
from itertools import accumulate

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 累積和
a = [0] + list(accumulate(A))
b = [0] + list(accumulate(B))

ans = 0
j = M
for i in range(N + 1):
    # Aで既にKを超えていたらBから取れない
    if a[i] > K:
        break
    # 選択可能な最大のjを探す
    # 最大のjは前回のj以下
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)

Buggy python submission (verdict: Runtime Error):
N, M, K = map(int, input().split())
A = list(map(int, input().split()))[::-1]
B = list(map(int, input().split()))[::-1]

t = 0
count = 0
while t <= K:
    if A and A[-1] < B[-1] and t + A[-1] <= K:
        t += A.pop()
        count += 1
    elif B and t + B[-1] <= K:
        t += B.pop()
        count += 1
    else:
        break
print(count)

Fixed submission:
from itertools import accumulate

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 累積和
a = [0] + list(accumulate(A))
b = [0] + list(accumulate(B))

ans = 0
j = M
for i in range(N + 1):
    # Aで既にKを超えていたらBから取れない
    if a[i] > K:
        break
    # 選択可能な最大のjを探す
    # 最大のjは前回のj以下
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        ans = -1
        continue
    if a == 0:
        ans = 0
        break
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np

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

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        ans = -1
        continue
    if a == 0:
        ans = 0
        break
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from math import prod

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

ans = prod(A)
if ans > 10**18:
    ans = -1
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

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

ans = reduce(lambda x, y: x * y, A)
if ans > 10**18:
    ans = -1
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

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

ans = reduce(lambda x, y: x * y, A)
if ans > 10**18:
    ans = -1
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    ans = -1
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

m = {}
for i, a in enumerate(A):
    m[i+1] = a

visited = []
cycle = set()
current_city = 1
visited.append(current_city)
cycle.add(current_city)
cycle_start_index = -1
while 1:
    current_city = m[current_city]
    if current_city in cycle:
        cycle_start_index = visited.index(current_city)
        break
    else:
        visited.append(current_city)
        cycle.add(current_city)

cycle_before = visited[:cycle_start_index]
cycle_after = visited[cycle_start_index:]
if len(cycle_before) > K:
    print(cycle_after[(K - len(cycle_before)) % len(cycle_after)])
else:
    print(cycle_before[K - 1])

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

m = {}
for i, a in enumerate(A):
    m[i+1] = a

visited = []
cycle = set()
current_city = 1
visited.append(current_city)
cycle.add(current_city)
cycle_start_index = -1
while 1:
    current_city = m[current_city]
    if current_city in cycle:
        cycle_start_index = visited.index(current_city)
        break
    else:
        visited.append(current_city)
        cycle.add(current_city)

cycle_before = visited[:cycle_start_index]
cycle_after = visited[cycle_start_index:]
if len(cycle_before) - 1 < K:
    print(cycle_after[(K - len(cycle_before)) % len(cycle_after)])
else:
    print(cycle_before[K])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(1, N+1):
    for j in range(i+A[i-1]+1, N+1):
        if abs(i - j) == A[i-1] + A[j-1]:
            ans += 1
print(ans)


Fixed submission:
from collections import defaultdict

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

mp = defaultdict(lambda: [0, 0])
for i in range(1, N+1):
    L = i + A[i-1]
    R = i - A[i-1]
    mp[L][0] += 1
    mp[R][1] += 1

ans = 0
for v in mp.values():
    ans += v[0] * v[1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
for i, s in enumerate(reversed(S)):
    x += int(s) * 10**i
    m = x % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)



Fixed submission:
from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
for i, s in enumerate(reversed(S)):
    x += int(s) * 10**i
    m = x % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)



Fixed submission:
from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
for i in range(0, n):
    s = S[i:]
    m = int(s) % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)



Fixed submission:
from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
for i in range(0, n):
    s = S[i:]
    m = int(s) % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)



Fixed submission:
from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)