Problem:


Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

1 ≤ |S| ≤ 200000

S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.



Sample input:
1817181712114


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = int(s)*pow(10,i) + x
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()
L = len(S)
res = 0

T = [0]
x = ""
for s in reversed(S):
    """ 累積和 """
    x = s + x
    T.append(int(x))

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

S = input()
L = len(S)
res = 0

T = [0]

for i in range(1,L+1):
    """ 累積和 """
    T.append(int(S[L-i:]))

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += c*(c-1)//2

print(res)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()
L = len(S)
res = 0

T = [0]

for i in range(1,L+1):
    """ 累積和 """
    T.append(int(S[L-i:]))

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()
L = len(S)
res = 0

T = [0]

for i in range(1,L+1):
    T.append(int(S[L-i:]))

reminder = defaultdict(int)
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder.values():
    res += combination(c,2)

print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mul = set(str(2019*i) for i in range(1,100))
ans = 0

for i in range(len(s)-3):
  p = 4
  while i+p<=len(s):
    if s[i:i+p] in mul:
      ans += 1
    p += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0

for i in range(len(s)):
  p = 4
  while i+p<=len(s):
    if int(s[i:i+p])%2019==0:
      ans += 1
    p += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
L = len(S)

res = 0
for i in range(L-3):
    for j in range(i+3, L):
        if not int(S[i:j+1])%2019:
            res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]
ans = 0

s = input()
n = len(s)
for size in range(1, n):
    for i in range(n - size + 1):
        if int(s[i:i + size]) % 2019 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    si = [int(i) for i in s]
    n = len(s)
    ndiv = 0
    m = 2019

    for i in range(5, n+1):
        sm = int(s[i-5:i]) % m
        if sm == 0:
            ndiv += 1
        for j in range(i, n):
            sm = (10 * sm + si[j]) % m
            if sm == 0:
                ndiv += 1

    print(ndiv)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    n = len(s)
    ndiv = 0
    pl = 10**5
    m = 2019

    for i in range(5, n+1):
        sm = int(s[i-5:i]) % m
        if sm == 0:
            ndiv += 1
        for j in range(i, n):
            sm = (10 * sm + int(s[j])) % m
            if sm == 0:
                ndiv += 1

    print(ndiv)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    ndiv = 0
    for i in range(len(s) - 4):
        for j in range(i + 5, len(s) + 1):
            if int(s[i:j]) % 2019 == 0:
                ndiv += 1

    print(ndiv)


main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
ls=len(s)
m=[0]*(2019)
m[0]+=1

cnt = 0
b=0
for i in range(ls):
  a = (b + int(s[ls - i -1])*10**cnt) % 2019
  m[a] += 1
  b = a
  cnt += 1

ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
m=[0]*(2019)
m[0]+=1

cnt = 0
b=0
for i in s[::-1]:
  a = (b + int(i)*10**cnt) % 2019
  m[a] += 1
  b = a
  cnt += 1


ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
S = input()

result = 0
if len(S) < 4:
    print(0)
    sys.exit(0)
for i in reversed(range(3, len(S))):
    keta = 3
    tmp = int(S[i-2:i+1])
    for j in reversed(range(i - 2)):
        tmp = int(S[j]) * (10 ** keta) + tmp
        if tmp % 2019 == 0:
            result += 1
        keta += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
S = input()

result = 0
for i in reversed(range(len(S))):
    keta = 0
    tmp = 0
    for j in reversed(range(i + 1)):
        tmp = int(S[j]) * (10 ** keta) + tmp
        if tmp % 2019 == 0:
            result += 1
        keta += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
# (Xl,0 − Xr−1,0) % 2019 = 0 → Xl,0 % 2019 = Xr−1,0 % 2019
cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 # 桁数が大きくなりすぎる → 10と2019が素だから可能な技

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
if int(len(s)) < 4 :
    print(0)
    exit()
c = 0
for i in range(4,int(len(s))):
    for j in range(0,int(len(s))-i+1):
        if int(s[j:j+i])%2019 == 0 :
            c+=1
print(c)
exit()

Submission status: Time Limit Exceeded

Solution code:
S=input() + ' '
if len(S) <= 4:
  print(0)
elif len(S) == 5:
  if int(S[:-1]) % 2019 == 0:
    print(1)
  else:
    print(0)
else:
  count = 0
  for i in range(len(S)-5):
    for j in range(i+4, len(S)):
      s = int(S[i:j])
      if s % 2019 == 0:
        count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
S=input() + ' '
if len(S) <= 4:
  print(0)
elif len(S) == 5:
  if int(S[:-1]) % 2019 == 0:
    print(1)
  else:
    print(0)
else:
  count = 0
  for i in range(len(S)-5):
    for j in range(i+4, len(S)):
      s = int(S[i:j])
      if s % 2019 == 0:
        count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

S = input()[::-1]

m = [0]*len(S)
tmp = 1
for i in range(len(S)):
    m[i] = int(S[i])*tmp%2019
    tmp *= 10

cum = [0]+[0]*len(S)
for i in range(1,len(S)+1):
    cum[i] = (cum[i-1]+m[i-1])%2019

d = {}
ans = 0
for i in range(len(cum)):
    if cum[i] not in d:
        d[cum[i]] = 1
    else:
        ans += d[cum[i]]
        d[cum[i]] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=str(input())

a=0
for i in range(0,len(s)-4):
    for j in range(i+4,len(s)+1):
        if (int(s[i:j]))%2019==0:
            a=a+1
print(a)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
li = []
dic = {}
ans = 0

s = 0
for i in range(len(S)):
  s += int(S[len(S)-1-i]) * (10**i)
  s = s % 2019
  if s == 0:
    ans += 1
  elif s not in li:
    li.append(s)
  elif s not in dic:
    dic[s] = 2
  else:
    dic[s] += 1
  
li = list(dic.values())
for l in li:
  ans += l * (l-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
li = []
dic = {}
ans = 0

for i in range(len(S)):
  s = int(S[i:]) % 2019
  if s == 0:
    ans += 1
  elif s not in li:
    li.append(s)
  elif s not in dic:
    dic[s] = 2
  else:
    dic[s] += 1
  
li = list(dic.values())
for l in li:
  ans += l * (l-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
li = [0]*2019
ans = 0

for i in range(len(S)):
  s = int(S[i:]) % 2019
  if s == 0:
    ans += 1
  else:
    li[s] += 1
  
for l in li:
  if l > 1:
    ans += l*(l-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
l = len(S)
ans = 0
for i in range(l-3):
  for j in range(i+4, l+1):
    s = int(S[i:j])
    if s % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=[]
for i in range(len(s)):
    t.append(int(s[i:]))
if s[len(s)-1]!="0":
    t.append(0)
t.sort()
mod=[0]*2019
calc=[0]*2019
for i in range(len(s)+1):
    mod[t[i]%2019]+=1
    if i>=5:
        for j in range(1,4):
            if t[i]%2019==t[i-j]%2019:
                calc[t[i]%2019]-=1
for i in range(2019):
    calc[i]+=mod[i]*(mod[i]-1)//2
    if calc[i]==-1:
        calc[i]=0
ans=0
for j in range(2019):
    ans+=calc[j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
num = len(s)

cnts = [1] + [0] * (2019 - 1)
for i in range(1, num+1):
    tmp = s[:i][::-1]
    cnts[int(''.join(tmp))%2019] += 1

ans = 0
for cnt in cnts:
    ans += (cnt-1)*cnt//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
num = len(s)

l = []
for i in range(1, num+1):
    tmp = s[:i][::-1]
    l.append(int(''.join(tmp)))

cnts = [1] + [0] * (2019 - 1)

for j in range(num):
    cnts[l[j] % 2019] += 1

ans = 0
for cnt in cnts:
    ans += (cnt-1)*cnt//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
import numpy as np

@jit
def solve():
    
    s = np.array(list(input())[::-1])
    num = len(s)
    #print(s, num)
    
    l = []
    for i in range(1,num+1):
        l.append(int(''.join(s[:i][::-1])))
    #print(l)
    l = np.array(l)
    mod = []
    for j in range(num):
        mod.append(l[j] % 2019)
    mod = np.array(mod)
    
    ans = 0
    for p in range(num):
        if mod[p] == 0:
            ans += 1
        tmp = 1
        for q in range(p+1,num):
            if mod[p] == mod[q]:
                tmp += 1
        ans += (tmp-1)*tmp//2
    
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

@jit
def solve():
    
    s = list(input())[::-1]
    num = len(s)
    #print(s, num)
    
    l = []
    for i in range(1,num+1):
        l.append(int(''.join(s[:i][::-1])))
    #print(l)
    
    mod = []
    for j in range(num):
        mod.append(l[j] % 2019)
    #print(mod)
    
    ans = 0
    for p in range(num):
        if mod[p] == 0:
            ans += 1
        tmp = 1
        for q in range(p+1,num):
            if mod[p] == mod[q]:
                tmp += 1
        ans += (tmp-1)*tmp//2
    
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]
num = len(s)

l = []
for i in range(1,num+1):
    l.append(int(''.join(s[:i][::-1])))

mod = []
for j in range(num):
    mod.append(l[j] % 2019)

ans = 0
for p in range(num):
    if mod[p] == 0:
        ans += 1
    tmp = 1
    for q in range(p+1,num):
        if mod[p] == mod[q]:
            tmp += 1
    ans += (tmp-1)*tmp//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
last = 0
for i in range(N):
    m = 10**(N-i-1)%MOD
    # val = (int(S[i])*m + nums[i])%MOD
    val = (int(S[i])*m + last)%MOD
    last = val
    # cnt += d[val]
    d[val] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
cnt = 0
# nums = [0]*(N+1)
last = 0
for i in range(N):
    m = 10**(N-i-1)%MOD
    # val = (int(S[i])*m + nums[i])%MOD
    val = (int(S[i])*m + last)%MOD
    last = val
    cnt += d[val]
    d[val] += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
s=input()
l=[0]*2019
l[0]=1
n=len(s)
for i in range(n):
  if s[i]=='0':
    continue
  l[int(s[i:])%2019]+=1
ans=0
for vv in l:
  ans+=vv*(vv-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
s=input()
l=[0]
n=len(s)
for i in range(n):
  if s[i]=='0':
    continue
  l.append(int(s[i:])%2019)
c=collections.Counter(l)
ans=0
v=c.values()
for vv in v:
  ans+=vv*(vv-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
cnt = 0
nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)%MOD
    val = (int(S[i])*m + nums[i])%MOD
    nums[i+1] = val
    cnt += d[val]
    d[val] += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)
# lS = list(map(int, list(S)))
# print(lS)

d = defaultdict(int)
d[0] += 1
cnt = 0
nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)
    val = int(S[i]) * m
    val %= MOD
    nums[i+1] = (val + nums[i])%MOD
    cnt += d[nums[i+1]]
    d[nums[i+1]] += 1
# nums.append(0)
# nums.reverse()
# print(nums)

# for i in range(N):
#     nums[i+1] += nums[i]
#     nums[i+1] %= MOD
#     # print(nums[i+1])
#     # print(d[nums[i+1]])
#     d[nums[i+1]] += 1
# # print(nums)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)
# lS = list(map(int, list(S)))
# print(lS)

nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)
    val = int(S[i]) * m
    val %= MOD
    nums[i+1] = val
# nums.append(0)
# nums.reverse()
# print(nums)

d = defaultdict(int)
d[0] += 1
cnt = 0
for i in range(N):
    nums[i+1] += nums[i]
    nums[i+1] %= MOD
    # print(nums[i+1])
    cnt += d[nums[i+1]]
    # print(d[nums[i+1]])
    d[nums[i+1]] += 1
# print(nums)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)
lS = list(map(int, list(S)))
# print(lS)

nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)
    val = lS[i] * m
    val %= MOD
    nums[i+1] = val
# nums.append(0)
# nums.reverse()
# print(nums)

d = defaultdict(int)
d[0] += 1
cnt = 0
for i in range(N):
    nums[i+1] += nums[i]
    nums[i+1] %= MOD
    # print(nums[i+1])
    cnt += d[nums[i+1]]
    # print(d[nums[i+1]])
    d[nums[i+1]] += 1
# print(nums)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
nS = int(S)
N = len(S)

nums = [0]
for i in range(N):
    m = 10**(N-i-1)
    val = nS//m * m
    val %= MOD
    nums.append(val)
    nS %= m
# nums.append(0)
# nums.reverse()
# print(nums)

d = defaultdict(int)
d[0] += 1
cnt = 0
for i in range(N):
    nums[i+1] += nums[i]
    nums[i+1] %= MOD
    # print(nums[i+1])
    cnt += d[nums[i+1]]
    # print(d[nums[i+1]])
    d[nums[i+1]] += 1
# print(nums)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
nS = int(S)
N = len(S)

nums = []
for i in range(N):
    val = (nS%10)*10**i
    val %= MOD
    nums.append(val)
    nS //= 10
nums.append(0)
nums.reverse()
# print(nums)

d = defaultdict(int)
d[0] += 1
cnt = 0
for i in range(N):
    nums[i+1] += nums[i]
    nums[i+1] %= MOD
    # print(nums[i+1])
    cnt += d[nums[i+1]]
    # print(d[nums[i+1]])
    d[nums[i+1]] += 1
# print(nums)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=input()
l=[]
i=1
while i*2019<=int(n):
  l.append(i*2019)
  i+=1
ans=0
for ll in l:
  ans+=n.count(str(ll))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
L = len(str(N))

count = 0
A = list(itertools.combinations(list(range(L)), 2))
for a in A:
    if a[1]-a[0] >= 3:
        if int(str(N)[a[0]:a[1]+1]) % 2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
from math import factorial

def permutations_count(n, r):
    ''' 順列 '''
    return factorial(n) // factorial(n - r)

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))


S = input()

lis = []

for i in range(1,len(S)+1):
    lis.append(int(S[-1*i:]) % 2019)

c = collections.Counter(lis)

su = 0

for k in c:
    if c[k] > 1:
        su += combinations_count(c[k], 2)
        
        
        
su += c[0]

print(su)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

s=int(input())
n=len(str(s))
lis=[0]*n
for i in range(n): lis[i]=s%(10**(i+1))%2019
lis=lis[::-1]
lis.append(0)
dic=dict(Counter(lis))
ans=0
for val in dic.values(): ans+=val*(val-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
modps = sorted([0]+[int(S[-i:])%2019 for i in range(1, len(S)+1)])
ans = 0
pre = -1
pre_cnt = 0
for modp in modps:
    if modp != pre:
        pre = modp
        pre_cnt = 1
    else:
        ans += pre_cnt
        pre_cnt += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()
ans = 0
N = len(S)
mod = 2019
dp = defaultdict(int)
cur = 0
for i in range(N, -1, -1):
    if i == N:
        dp[0] += 1
    else:
        cur += ((10 ** (N - i - 1)) * int(S[i])) % mod
        cur %= mod
        dp[cur] += 1
for v in dp.values():
    if v > 1:
        ans += v * (v - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

S = input()
ans = 0
# i + 1文字目以降の数字列を2019で割った余りをdp[i]とするとdp[i - 1] == dp[j](mod 2019)の時(i, j)が条件を満たす
N = len(S)
mod = 2019
dp = [0] * (N + 1)
for i in range(N, -1, -1):
    if i == N:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + (10 ** (N - i - 1)) * int(S[i])) % mod

count = Counter(dp).most_common()
for k, v in count:
    if v > 1:
        ans += v * (v - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
for i in range(1, len(s)+1):
    a[int(s[:i][::-1])%2019] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    if x >= 2:
        ans += comb(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
for i in range(1, len(s)+1):
    a[int(s[:i][::-1])%2019] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    ans += comb(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    S = list(map(int, LS()))
    S = S[::-1]
    ln = len(S)
    mod = 2019

    times = 1
    for i in range(ln):
        S[i] = S[i] * times % mod
        times = times * 10

    R = [0] * (ln+1)
    memo = {0: 1}
    ans = 0
    for i in range(1, ln+1):
        tmp = (R[i-1] + S[i-1]) % mod
        R[i] = tmp
        cnt = memo.get(tmp, 0)
        ans = ans + cnt
        memo[tmp] = cnt + 1
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

s = input()
ls = []
for i in range(1, len(s)+1):
    ls.append(int(s[len(s)-i:]))

a = defaultdict(int)
a[0] += 1
for i in range(len(s)):
    a[ls[i]%2019] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    ans += comb(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
s = input()
ls = []
for i in range(1, len(s)+1):
    ls.append(int(s[len(s)-i:]))

arr = [0 for i in range(len(s)+1)]
for i in range(len(s)):
    arr[i+1] = ls[i]%2019

def comb(a):
    return a*(a-1)//2

m = Counter(arr)
ans = 0
for x, y in m.items():
    ans += comb(y)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0
for i in range(4, len(S) + 1):
    for j in range(0, len(S) - i + 1):
        if int(S[j:j + i]) % 2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = int(s)
p = ""
c = 0
for i in range(0, len(s)-3):
    k = 0

    while(i+4+k <=len(s)):
        p = s[i:i+4+k]
        k += 1
        if int(p)%2019 == 0:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
s=input()
s=s[::-1]
l=[0]*2019
l[0]=1
prev=0
ans=0

for i in range(len(s)):
  mul=(10**i)%2019
  now=(int(s[i])*mul)%2019
  ans+=l[(prev+now)%2019]
  l[(prev+now)%2019]+=1
  prev=(prev+now)%2019

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod2019 = [0]*len(S)

for i in range(len(S)):
    mod2019[i] = int(S[i:])%2019

mod2019.extend([0])

answer = 0
count = [0 for _ in range(2020)]

for i in range(len(S)+1):
    answer += count[mod2019[i]]
    count[mod2019[i]] += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod2019 = [0]*len(S)

for i in range(len(S)):
    mod2019[i] = int(S[i:])%2019

mod2019.append(0)

answer = 0
count = [0 for _ in range(2020)]


for i in range(len(S)+1):
    answer += count[mod2019[i]]
    count[mod2019[i]] += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
s = input()

count = 0
for i in range(0, len(s)-1):
  for j in range(i + 4, len(s)+1):
    if int(s[i:j]) % 2019 == 0:
      count += 1
      
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    count = 0

    if len(S)<=200000:
        for i in range(len(S)-4):
            for j in range(i+4, len(S)+1):
                tmp = int(S[i:j])
                if pow(tmp,1,2019)==0:
                    count += 1

    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    count = 0

    if len(S)<=200000:
        for i in range(len(S)-4):

            for j in range(i+4, len(S)+1):
                tmp = int(S[i:j])
                if tmp%2019==0:
                    count += 1

    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

if len(S)<=200000:
    for i in range(len(S)-4):
        for j in range(i+4, len(S)+1):
            tmp = int(S[i:j])
            if tmp%2019==0:
                count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

if len(S)<=200000:
    for i in range(len(S)-4):
        for j in range(i+3, len(S)+1):
            tmp = int(S[i:j])
            if tmp%2019==0:
                count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

if len(S)>3:
    for i in range(len(S)-4):
        for j in range(i+3, len(S)+1):
            tmp = int(S[i:j])
            if tmp%2019==0:
                count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

for i in range(len(S)-4):
    for j in range(i+3, len(S)+1):
        tmp = int(S[i:j])
        if tmp%2019==0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# 答え見た
s = input()
mod = [0]*2019
mod[0] += 1
count = 0
for i in range(len(s)):
    mod[int(s[i:])%2019] += 1

for j in range(2019):
    m = mod[j]
    if m >= 2:
        count += 0.5*m*(m-1)
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    memo[num] += 1
    t *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
ten = 1
for i in reversed(s):
    num += int(i) * ten
    memo[num%2019] += 1
    ten *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
s = s[::-1]

memo = [0] * 2019
memo[0] += 1

num = 0
ten = 1
for i in s:
    num += int(i) * ten
    memo[num%2019] += 1
    ten *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
ten = 1
for i in range(n):
    num += int(s[-(i+1)]) * ten
    memo[num%2019] += 1
    ten *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = ""
for i in range(n):
    num = s[-(i+1)] + num
    num_int = int(num)
    memo[num_int%2019] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ss = [0 for _ in range(len(s)+1)]

for i in range(0, len(s)):
    ss[i] = int(s[i:])

ans = set()
for index in range(len(s)):
    i = index
    j = i+3
    while True:
        if j > len(s):
            break
        tmp = ss[i]-ss[j]
        #print(ss[i]-ss[j])
        if tmp % 2019 == 0:
            #print(i,j)
            ans.add((i+1,j))
            i = j-1
        j+=1
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
g=0
n=list(map(int,input()))
L=len(n)

for i in range(L):
  num=0
  for j in range(L-i):
    num=num*10+int(n[i+j])
    
    ans=int(num)%2019
    if ans==0:
      g=g+1
print(g)

Submission status: Time Limit Exceeded

Solution code:
def main():

    S = input()

    count = 0

    for i in range(len(S)):
        if i + 3 not in range(len(S)):
            break

        residue = int(S[i:i+4]) % 2019

        if residue == 0:
            count += 1

        for j in range(i+4, len(S)):
            residue = (residue * 10 + int(S[j])) % 2019

            if residue == 0:
                count += 1

    print(count)


def input_int():
    return int(input())


def input_ints():
    return map(int, input().split())


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int, q: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()