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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = STR()
arr = [-1 for _ in range(len(s))]
tmp = 0
for i in range(len(s)):
    tmp = tmp + int(s[i]) * (10 ** (len(s) - i))
    arr[i] = tmp % 2019
a = list(set(arr))
b = Counter(arr)
ans = 0
for i in a:
    tmp = b[i]
    if i == 0:
        ans += (tmp + 1) * tmp // 2
    else:
        ans += tmp * (tmp - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = [0]*len(s)
t[-1] = int(s[-1])
for i in range(len(s)-2,-1,-1):
    p = int(s[i])*(10**(len(s)-1-i))%2019
    t[i] = (p+t[i+1])%2019

u = sorted(t)
ans = 0

if u[0] == 0:
    ans += 1
for i in range(len(s)-1):
    if u[i] == u[i+1]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
unko=[0]*2019
tmp=0
num=1
for s in S[::-1]:
  s=int(s)
  tmp+=num * s
  num=num*10
  unko[tmp%2019]+=1
ans=0
ans+=(unko[0]+1)*unko[0]/2
for i in unko[1:]:
  ans+=i*(i-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
s = [int(s) for s in S]
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += s.pop()*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)

l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * pow(10,index)
    temp %= 2019
    l[temp] += 1
    index += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

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

s2 = [0 for _ in range(n)]

zero = []
one = []
two = []
s2[0] = int(s[0]) % 3
if s2[0] == 0:
  zero.append(0)
elif s2[0] == 1:
  one.append(0)
elif s2[0] == 2:
  two.append(0)
for i in range(1,n):
  s2[i] = s2[i-1] + int(s[i])
  s2[i] %= 3
  if s2[i] == 0:
    zero.append(i)
  elif s2[i] == 1:
    one.append(i)
  elif s2[i] == 2:
    two.append(i)
ans = 0
length = len(zero)
for i in range(length):
    if int(s[:zero[i]+1]) % 2019 == 0:
      ans += 1
length = len(zero)
for i in range(length-1):
  tmp = s[zero[i]+1:]
  for j in range(i+1,length):
    if int(tmp[:zero[j]-zero[i]]) % 2019 == 0:
      ans += 1

length = len(one)
for i in range(length-1):
  tmp = s[one[i]+1:]
  for j in range(i+1,length):
    if int(tmp[:one[j]-one[i]]) % 2019 == 0:
      ans += 1

length = len(two)
for i in range(length-1):
  tmp = s[two[i]+1:]
  for j in range(i+1,length):
    if int(tmp[:two[j]-two[i]]) % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
N = len(S)
ans1 = [0] * 2019
ans2 = 0

T = [0] *  (N + 1)
T[N] = 0
ans1[0] += 1

for i in range(N - 1, -1, -1):
  #print(i)
  T[i] = (T[i + 1] + 10 ** (N - i - 1) * int(S[i])) % 2019
  ans1[T[i]] += 1

for i in range(2019):
  x = ans1[i]
  ans2 += x * (x - 1) / 2
  
#print(ans1[0])
#print(T)
print(int(ans2))

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
mod = []
for i in range(len(s)):
    mod.append(int(s[i:])%2019)
for i in range(1,2019):
    ans += mod.count(i)*(mod.count(i)-1)/2
ans += mod.count(0)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta *= 10


cmod = Counter(smod)
#print(cmod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import collections
S = input()[::-1]
N = len(S)
mod = 2019

x = [0] * N
x[0] = int(S[0]) % mod

for i in range(1, N):
    x[i] = ((10 ** i) * int(S[i]) + x[i - 1]) % mod

d = collections.Counter(x)
target = [v for k, v in d.items() if v > 1]

ans = 0
ans += sum([t * (t - 1) // 2 for t in target])

if 0 in d.keys():
    ans += d[0] * (d[0] - 1) // 2 + d[0]
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S_dig = [0] * (N + 1)
for i in range(N):
    S_dig[i] = int(S[i:]) % 2019
x = 0
sum = 0
for i in range(2019):
    x = S_dig.count(i)
    sum += x * (x-1) // 2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = STR()
arr = [-1 for _ in range(len(s))]
tmp = 0
for i in range(len(s)):
    tmp = tmp + int(s[i]) * (10 ** (len(s) - i))
    arr[i] = tmp % 2019
a = list(set(arr))
b = Counter(arr)
ans = 0
for i in a:
    if i == 0:
        ans += (b[i] + 1) * b[i] // 2
    else:
        ans += b[i] * (b[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

for i in range(len(S)):
    lists[int(S[i:]) % 2019] += 1

for i in range(2019):
    if lists[i] >= 2:
        ans += (lists[i] * (lists[i] - 1)) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
for i in range(len(s)):
  a+=s[i]*(10**i)
  b=a%2019
  l[b]+=1

answer=0
for i in range(2019):
  answer+=l[i]*(l[i]-1)//2
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S=input() # 文字入力
length = len(S)
count=0
for i in range(length-3):
    num = int(S[i: i+4])%2019
    if num==0:
        count+=1
    
    for j in range(i+4, length) :
        temp = int(S[j])%2019
        num = (num*10) % 2019
        num = (num+temp) % 2019
        
        if num == 0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    S = input()
    result = 0
    t = [0]
    for i in range(len(S)):
        t.append((t[-1]+int(S[-i-1])*10**i) % 2019)
    count_dict = collections.Counter(t)
    for a, b in count_dict.items():
        result += b*(b-1) // 2

    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

c=0
def check2019(S, n):
    global c
    s = int(S)
    if s%2019 ==0 and s>2018:
        c +=1
    else:
        pass
    if s>9999:
        if n ==0:
            return check2019(S[1:],1), check2019(S[:-1], 0)
        else:
            return check2019(S[1:],1)
    else:
        return 0
S = input().rstrip("\n")
c =0

if len(S) >= 4:
    check2019(S, 0)
else:
    pass
print(c)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

for i in range(len(S)):
    lists[int(S[i:]) % 2019] += 1

for i in range(2019):
    if lists[i] >= 2:
        ans += (lists[i] * (lists[i] - 1)) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:28:26 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
dic = {}
mod = 2019
count = 0

for i in range(1,n+1):
    num = int(s[n-i:n])
    num = num%mod
    if num in dic:
        dic[num] += 1
    if num not in dic:
        dic[num] = 1

ans = 0
for fact in dic:
    ans += dic[fact]*(dic[fact]-1)//2
if 0 in dic:
    ans += dic[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

def resolve():
    s = input()

    mod_table = np.zeros(shape=len(s), dtype=int)
    for i in reversed(range(len(s) - 1)):
        mod_table[i] = int(s[i:]) % 2019

    count = Counter(mod_table)
    vals = np.array(list(count.values()))

    ans = sum((vals * (vals - 1)) / 2)
    print(int(ans))
resolve()

Submission status: Time Limit Exceeded

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

temp = [0]*2019
num = 0
for i in range(n):
    num += int(s.pop())*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()

mod = 2019
d = defaultdict(int)
t = 0
for i, v in enumerate(S[::-1]):
    t = (t + int(v) * 10 ** i) % mod
    d[t] += 1

ans = 0
for v, c in d.items():
    if v == 0:
        ans += c
    elif c > 1:
        ans += c * (c - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = STR()
arr = [-1 for _ in range(len(s))]
for i in range(len(s)):
    arr[i] = int(s[i:]) % 2019
a = list(set(arr))
b = Counter(arr)
ans = 0
for i in a:
    if i == 0:
        ans += (b[i] + 1) * b[i] // 2
    else:
        ans += b[i] * (b[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)

l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * pow(10,index)
    l[temp%2019] += 1
    index += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
data = []
for i in range(l):
  data.append(int(s[i:l]) % 2019)
data.append(0)
print(len(data)-len(set(data)))

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0
for i in range(len(s)+1):
    for j in range(i+1, len(s)+1):
        if (int(s[i:j])%3 == 0 and int(s[i:j])%673 == 0):
            count += 1
            #print("ok", s[i:j])
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    S = sr()
    N = len(S)
    a = defaultdict(int)
    a[0] += 1
    t = 0
    for i in range(N):
        t += int(S[-1-i])*pow(10, i)
        a[t%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

S = input().strip()
l = len(S)
dic = {0:[-1]}
dp = [[0 for _ in range(2019)] for i in range(l)]
ans = 0
mod = 0
for i in range(0, l):
    s = int(S[i:])
    mod = s % 2019
    if mod in dic:
        dic[mod].append(i)
    else:
        dic[mod] = [i]

for key, val in dic.items():
    v_len = len(val)
    ans += (v_len * (v_len -1))// 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


y = 2019
S = [s for s in input()]
N = len(S)
T = [0] * N

for i in range(N):
    T[i] = int(''.join(S[i:N])) % y

cnt = 0
for t, c in Counter(T).items():
    if t == 0:
        cnt += 1
        continue
    cnt += c * (c - 1) // 2
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()

length = len(S)

cnt = 0
temp = int(S[ : 4])
for x in range(length):
    first = temp
    for i in range(x + 4, length + 1):
        temp %= 2019
        if temp == 0:
            cnt += 1
        #print(temp, cnt)

        if i < length:
            temp = ((temp % 2019) * 10) % 2019
            temp = (temp + int(S[i])) % 2019
        else:
            if x + 4 < length:
                temp = (first - (int(S[x]) * 1000))
                temp = temp * 10 + int(S[x + 4])


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

s = input()
mod = 2019
array = [0]*mod

for i in range(len(s)):
    array[int(s[i:len(s)]) % mod] += 1
    
array[0] += 1
    
cnt = 0
for i in range(mod):
    if array[i] > 1:
        cnt += factorial(array[i]) / (factorial(2)*factorial(array[i] - 2))
        
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import bisect

s = input()
n = len(s)

s2 = [0 for _ in range(n)]

zero = []
one = []
two = []

for i in range(n):
  s2[i] = int(s[i]) % 3

for i in range(1,n):
  s2[i] += s2[i-1]
  s2[i] %= 3

for i in range(n):
  if s2[i] == 0:
    zero.append(i)
  elif s2[i] == 1:
    one.append(i)
  elif s2[i] == 2:
    two.append(i)
ans = 0
length = len(zero)
for i in range(length):
    if int(s[:zero[i]+1]) % 2019 == 0:
      ans += 1
length = len(zero)
for i in range(length-1):
  tmp = s[zero[i]+1:]
  for j in range(i+1,length):
    if int(tmp[:zero[j]-zero[i]]) % 2019 == 0:
      ans += 1

length = len(one)
for i in range(length-1):
  tmp = s[one[i]+1:]
  for j in range(i+1,length):
    if int(tmp[:one[j]-one[i]]) % 2019 == 0:
      ans += 1

length = len(two)
for i in range(length-1):
  tmp = s[two[i]+1:]
  for j in range(i+1,length):
    if int(tmp[:two[j]-two[i]]) % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    S = input().rstrip()

    N = len(S)
    S = int(S)

    M = [0 for i in range(2019)]

    for i in range(N+1):
        T = S % (10**i)
        M[T%2019] += 1

    res = 0

    for m in M:
        res += m * (m-1) // 2


    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = len(S)
table = [-1] * N
T = [-1] * N
prev = 0
for i, s in enumerate(reversed(S)):
    prev += (int(s) * (10 ** i)) % 2019
    prev %= 2019
    T[i] = prev

DP = [0] * 2019
for t in T:
    DP[t] += 1

ans = DP[0]
for num in DP:
    ans += num * (num - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(input())
    N = len(S)

    P = 2019
    num = [0] * P
    num[0] = 1
    now, ans = 0, 0
    _10 = 1
    for s in S[::-1]:
        now = (now + int(s)*_10) % P
        _10 *= 10
        ans += num[now]
        num[now] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
data = []
for i in range(len(s)):
  data.append(int(s[i:len(s)]) % 2019)
data.append(0)
print(len(data)-len(set(data)))

Submission status: Time Limit Exceeded

Solution code:

def main():
    s = input()
    amari_lst = [0] * len(s)
    num_lst = []
    for i in range(len(s)):
        temp = int(s[i:])
        num_lst.append(temp)
        amari_lst[i] = temp % 2019
    #print(amari_lst)
    counter = 0
    for i in range(len(s)-3):
        #print(num_lst[i])
        if amari_lst[i] == 0 and num_lst[i] >= 2019:
            counter += 1
        counter += amari_lst[i+3:].count(amari_lst[i])

    print(counter)
    #print(num_lst)
    #print(amari_lst)







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()
A = [0 for _ in range(len(S))]
A[-1] = int(S[-1])%3
for i in range(2,len(S)+1):
    A[-i] = (A[-i+1]+int(S[-i]))%3
B = [0 for _ in range(len(S))]
B[-1] = int(S[-1])%673
for i in range(2,len(S)+1):
    B[-i] = (int(S[-i])*10**(i-1)+B[-i+1])%673
C = {}
for i in range(len(S)):
    a = A[i]
    b = B[i]
    if (a,b) not in C:
        C[(a,b)] = 0
    C[(a,b)] += 1
if (0,0) in C:
    C[(0,0)] += 1
cnt = 0
for c in C:
    n = C[c]
    cnt += (n*(n-1))//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

s = input()
n = len(s)
T = [0]*(n+1)
T[n] = 0
T[n-1] = int(s[n-1])
for i in range(n-2, -1, -1):
    T[i] = (T[i+1] + int(s[i])*(10**(n-i-1)))%2019

c = Counter(T)
res = 0
cc = list(dict(c).values())

for ele in cc:
    if ele>=2:
        res += ele*(ele-1)//2

print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()

c = [0] * 2019
c[0] = 1
for i in range(len(S)):
    c[int(S[i:])%2019] += 1

ans = 0
for m in c:
    ans += m * (m - 1) / 2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
c = 0
for st in range(len(S)):
    for end in range(st + 4, len(S)+1):
        if 0 == int(S[st:end]) % 2019:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(input())
    s = s[::-1]

    l = [[] for i in range(673)]
    l[0].append(0)
    ten = 1
    mod = 673
    now = 0
    for i in range(len(s)):
        now = (now+int(s[i])*ten)%mod
        l[now].append(i+1)
        ten *= 10
        ten %= mod
    ans = 0
    for i in l:
        if len(i) >= 2:
            for j in range(len(i)-1):
                for k in range(j+1,len(i)):
                    a = sum(list(map(int,s[i[j]:i[k]])))
                    if a %3 == 0:
                        ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
S = input().strip()
N = len(S)

mod_count = {0: 1}
for mod in [int(S[i:]) % 2019 for i in range(N)]:
    mod_count[mod] = mod_count.get(mod, 0) + 1

print(sum([m * (m - 1) for m in mod_count.values()]) // 2)

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    S = input()
    val = 0
    ans = 0

    for i in range(len(S) - 3):
        
        for j in range(i + 4, len(S) + 1):

            val = int(S[i:j])
            
            if val % 2019 == 0:
                ans += 1
    
    print('{}'.format(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
ans = 0
s = input()
size = len(s) + 1
for i in range(size):
    if (i + 4) >= size:
        continue
    for j in range(i + 4,  size):
        if ((int(s[i:j]) % 2019) == 0 ):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
T = []
for i in range(len(S)):
    T.append((int("".join(S[i:])))%2019)

ans = 0
for i in range(len(T)):
    if T[i] == 0:
        ans += 1
print(ans + len(T)-len(set(T)))

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

S = input()
S = S[::-1]

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S):
	a = a + (int(s) * (10 ** i))
	
	ans += A[a%m]
	A[a%m] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    S = [s for s in sr()]
    N = len(S)
    a = defaultdict(int)
    a[0] += 1
    t = ''
    for i in range(N):
        t = S.pop()+t
        a[int(t)%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
s=int_([*input()])
dp=zeros((len(s)+1,2019),int)
r=arange(2019)
a=0
for i,c in enumerate(s):
  dp[i+1,(r*10+c)%2019]+=dp[i,r]
  dp[i+1,c]+=1
print(sum(dp[:,0]))

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

S = input()

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S[::-1]):
	a = a + (int(s) * (10 ** i))
	
	ans += A[a%m]
	A[a%m] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

s = input()
n = len(s)
T = [0]*(n+1)
T[n] = 0
T[n-1] = int(s[n-1])
for i in range(n-2, -1, -1):
    T[i] = (T[i+1] + int(s[i])*(10**(n-i-1)))%2019

c = Counter(T)
res = 0
cc = list(dict(c).values())

for ele in cc:
    res += ele*(ele-1)//2

print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

for i in range(len(S)):
    mod = int(S[i:]) % 2019
    mod_bucket[mod] += 1

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 *= 10
for i in dp:
    ans += i * (i-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    
    cnts[sum_of_digits] += 1
 
ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
*s,=map(int,input())
dp=zeros((len(s)+1,2019),int)
r=arange(2019)
a=0
for i,c in enumerate(s):
  dp[i+1,(r*10+c)%2019]+=dp[i,r]
  dp[i+1,c]+=1
print(sum(dp[:,0]))

Submission status: Time Limit Exceeded

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

for i in range(len(s)):
    array[i] = int(s[i:len(s)]) % mod
    
array[len(s)] = 0

cnt = 0

for i in range(0, len(array)-1):
    for j in range(i+1, len(array)):
        if array[i] == array[j]:
            cnt += 1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# s = input()
# n = len(s)

# if n < 4:
#     print(0)
#     sys.exit()

# ans = 0
# for i in range(n-3):
#     for j in range(i+3, n):
#         a = int(s[i:j+1])
#         # print(i, j, a, a%2019)
#         if a % 2019 == 0:
#             ans += 1
#             print(a)
# print(ans)

# count = 0
# s = input()
# a = int(s) // 2019
# print(a)
# for i in range(a):
#     if str(i*2019) in s:
#         print(str(i*2019))
#         count += 1
# print(count)

import numpy as np
import math
from collections import defaultdict, Counter

s = input()
n = len(s)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

res = [int(s[a:])%2019 for a in range(n)] + [0]

ans = 0
count = Counter(res)
for i in range(2019):
    ans += (count[i] * (count[i] - 1)) // 2
print(ans)
# num, count = np.unique(res, return_counts=True)
# ans = 0

Submission status: Time Limit Exceeded

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

remainder=[0]*2019
s=''
ans=0
for i in range(N-1,-1,-1):
  s=S[i]+s
  T=int(s)
  n=T%2019
  remainder[n]+=1
  if remainder[n]!=1:
    ans+=remainder[n]-1
ans+=remainder[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
 
 
l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * 10**index
    l[temp%2019] += 1
    index += 1
 
ans = l[0]
 
for i in range(1, 2019):
    v = l[i]
    ans += v * (v-1) // 2
 
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()

mods = []
n = 0
r = 0
e = 0
for i in reversed(range(len(S))):
	#n = int(S[i:])
	n += int(S[i]) * 10**e
	e += 1
	m = n % 2019
	mods.append(m)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
mem_mod = [0 for i in range(0,2019,1)]
N = len(S)
counter = 0
S_num_tmp = list(S)
S_num = list(map(int, S_num_tmp))
tmp=10

for i in range(1,N,1):
    S_num[N-i-1] = (S_num[N-i] + ((tmp)*S_num[N-i-1]))%2019
    tmp=tmp*10

for i in range(0,N,1):
    X = S_num[N-i-1]
    if X==0:
        counter+=1
    counter += mem_mod[X]
    mem_mod[X] += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
S = str(input())
n = len(S)
mods = [int(S[i:])%2019 for i in range(n)][::-1]
c = collections.Counter(mods)
count = 0
for s in c.values():
    if s >= 2:
        count += comb(s,2)
count += c[0]
print(count)

Submission status: Time Limit Exceeded

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

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

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def resolve():
    S = [s for s in sr()]
    N = len(S)
    a = [0]*(N+1)
    t = ''
    for i in range(N):
        t = S.pop()+t
        a[i] = int(t)%2019
    A = Counter(a)
    ans = 0
    for n in A.values():
        ans += n*(n-1)//2
    print(ans)
resolve()

Submission status: Time Limit Exceeded

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

remainder=[0]*2019
s=''
for i in range(N-1,-1,-1):
  s=S[i]+s
  T=int(s)
  n=T%2019
  remainder[n]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)


l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * 10**index
    l[temp%2019] += 1
    index += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
s=s[::-1]
mod = 2019
li = [0]*(len(s)+1)
cnt=1
for i in range(len(s)):
    li[i+1]=li[i] + int(s[i]) * cnt
    li[i+1]%=mod
    cnt*=10
import collections
A=collections.Counter(li[1:]);ans=0
for u,v in A.items():
    ans+=v*(v-1)//2
    if u==0:
        ans+=v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main(s):
    ketasuu = len(s)
    c = int("9"*ketasuu) // 2019
    res = 0
    for i in range(1,c+1):
        tar = str(2019*i)
        res += s.count(tar)
    return res

s = input()
print(main(s))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    for i in range(len(S)):
        mod = int_S % (10**(i+1)) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)