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
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def main():
    S = input().strip()[::-1]
    MOD = 2019
    T = [0, int(S[0])]
    for d, s in enumerate(S):
        if d == 0:
            continue
        tmp = int(s) * (10**d)
        T.append((T[-1] + tmp) % MOD)

    # print(T)

    cT = Counter(T)
    # print(cT)
    ans = 0
    for k in T:
        cT[k] -= 1
        ans += cT[k]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i))%2019
  mod[s]+=1
answer=0
for i in mod:
  answer+=i*(i-1)//2
print(answer)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
s_int=[0]*n
x=pow(10,n-1)
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Submission status: Time Limit Exceeded

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

if l <= 3: 
    print(0)
else:
    ans = 0 
    for i in range(l-3):
        for j in range(i+4,l+1):
            v = s[i:j]
            
            if (int(v) % 2019) == 0 :
                ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=[int(j) for j in input()][::-1]
m=len(s)
from collections import Counter
c=Counter()
tmp=0
c[0]+=1
t=1
for i in range(m):
    tmp+=t*s[i]
    c[tmp%2019]+=1
    t*=10
ans=0
for i in c:
    j=c[i]
    ans+=j*(j-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#input
S = str(input())

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N+1)

for i in range(1, N+1):
    dp[i] = int(S[-i::]) % 2019

T = Counter(dp[1:])

answer = 0
answer += T[0]

for t in T.values():
    if t >= 2:
        answer += t*(t-1)//2

print(answer)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#input
S = str(input())

#output
import numpy as np
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = np.zeros(N+1, int)

for i in range(1, N+1):
    dp[i] = int(S[-i::]) % 2019

T = Counter(dp[1:])

answer = 0
answer += T[0]

for t in T.values():
    if t >= 2:
        answer += t*(t-1)//2

print(answer)

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))

Submission status: Time Limit Exceeded

Solution code:
a=input()
list1=[]
current_num=int(a[-1])%2019
previous_num1=1
length=len(a)
list1.append(current_num)
for i in range(2,len(a)+1) :
    previous_num1 =(10*previous_num1)%2019
    
    current_num=(int(a[-i])*previous_num1 + current_num) % 2019
    list1.append(current_num)
count=0


list2=[]
for i in range(len(a)) :
  list2.append(int(a[i:])%2019)

count=0
list1.append(0)
import collections
c=collections.Counter(list1)
list2=c.values()
count=0
for item in list2 :
    count+=(int(item*(item-1)/2))


print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
for i in range(l):
    dp = dp + pow(10,i)*int(S[-1-i])
    mod[dp % 2019] += 1
mod[0] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
sn=[0]*n
x=pow(10,n-1)
for i in range(n):
    sn[i]=(int(s[i])*x)%2019
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-sn[i-1]
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
S = input()
M = 2019
dp = [0] * M
dp[0] = 1
t = 0
for i, s in enumerate(S[::-1]):
    t = (t + int(s) * (10 ** i)) % M
    dp[t] += 1

r = 0
for d in dp:
    r += d * (d - 1) // 2

print(r)

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=s+int(string[-1-i])*pow(10,i)
  mod[s%2019]+=1
print(sum([i*(i-1)//2 for i in mod]))

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
sn=[0]*n
x=pow(10,n-1)
for i in range(n):
    sn[i]=(int(s[i])*x)%2019
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-sn[i-1]
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int,list(input())))
n = len(s)

mod = [0]*2019
mod[0] = 1
pre = 0
for i in reversed(range(n)):
    pre = (pre + s[i]*10**(n-i-1))%2019
    mod[pre] += 1
print(sum([m*(m-1)//2 for m in mod]))

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
for i in range(l):
    dp = dp + pow(10,i)*int(S[-1-i])
    mod[dp % 2019] += 1
mod[0] += 1
cnt = 0
for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def sum_m(m):
    return m*(m-1)//2
S=str(input())
n=len(S)
mod=2019
ans=0
mod_set=set()
box=[0 for i in range(n)]
T=[0 for i in range(n+1)]
T[n-1]=int(S[n-1])
box[n-1]=1
for i in range(n-2,-1,-1):
    box[i]=box[i+1]*10%mod
    a=int(S[i])*box[i]+T[i+1]
    k=a%mod
    T[i]=k
    mod_set.add(k)
for i in mod_set:
    m=T.count(i)
    ans+=sum_m(m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(sum([i*(i-1)//2 for i in mod]))

Submission status: Time Limit Exceeded

Solution code:
import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()[::-1]

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i, j in enumerate(s):
	ai[i] = (int(j)*pow(10,i,p))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  S_string = input()
  S_string += "0"
  dist = [0 for _ in range(2019)]
  dist[0] = 1
  for i in range(len(S_string) - 1):
    dist[int(S_string[i:])%2019] += 1

  ans = 0
  for xi in dist:
    ans += max(0, xi * (xi - 1) // 2)
  print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i in range(len(s)):
  n=(n+int(s[-1-i])*(10**i)%2019)%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
sn=[0]*n
x=pow(10,n-1)
for i in range(n):
    sn[i]=int(s[i])*x
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-sn[i-1]
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod if i > 1])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
s = input()
dct = defaultdict(int)
dct[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x += int(c)*d
    dct[x%2019] += 1
    d *= 10
ans = 0
for v in dct.values():ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
ok = 0
test = str()

for i in range(0, len(S) + 1):
    for j in range(i, len(S) + 1):
        if j - i <= 3:
            continue
        bun = int(S[i:j])
        if bun % 2019 == 0:
            ok += 1

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
cnt = 0
ss = []
nums = np.array([(i+1)*2019 for i in range(200000//2019) if not "0" in str((i+1)*2019)])
for start in range(len(s)):
  end = start + 3
  while(end+1<=len(s)):
    if int(s[start:end+1]) in nums:
      cnt += 1
    end += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()[::-1]

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[i])*pow(10,i,p))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = input()
mods = [0]*2019
mods[0] += 1
for i in range(len(s)):
    value = int(s[i:])
    mods[value % 2019] += 1
print(sum([mod*(mod-1)//2 for mod in mods]))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*(k%2019))%2019
      k*=10
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
string=input() #入力文字列
length=len(string) #入力文字列の長さ
mod=[1]+[0]*2018 #出てきたmod値を加算するようの箱
while length > 0: #後ろから頭まで
  s = int(string[length-1:]) 
  mod[s%2019]+=1
  length-=1
answer=0
for i in mod:
  answer+=int(i*(i-1)/2)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
l = len(S)
dp = int(S[-1])
suml = [dp]
for i in range(l-1):
    dp = dp + pow(10,(i+1))*int(S[-2-i])
    suml.append(dp % 2019)
mod = {0:1}
for a in suml:
    if a in mod.keys():
        mod[a] += 1
    else:
        mod[a] = 1
cnt = 0
for a in mod:
    if mod[a] > 1:
        cnt += (mod[a]*(mod[a]-1))//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_dic = {}
count = 0

for i in range(len(N)+1):
  for j in range(i+1, len(N)+1):
    if int(N[i:j]) not in N_dic:
      N_dic[int(N[i:j])] = 1
    else:
      N_dic[int(N[i:j])] += 1
      
for k, v in N_dic.items():
  if k % 2019 == 0:
    count += v
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import collections
  s = input()
  r = []
  x = 0
  for i in range(len(s)):
    x += int(s[-i-1])*pow(10,i)
    x %= 2019
    r.append(x)
  d = collections.Counter(r) 
  ans = 0
  if 0 in d:
    ans += d[0]
  for k,v in d.items():
    if v >= 2:
      ans += v*(v-1)//2
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
    
def abs(num):
    if num < 0:
        return -num
    else:
        return num

###
# main
if(__name__ == '__main__'):
    # input
    s = input()
    len_s = len(s)

    ans = 0
    if len_s >= 4:
        dic_a = {}
        dic_b = {}
        for i in range(2019):
            dic_a[i] = 0
            dic_b[i] = 0
        dic = [dic_a, dic_b]
        current = 0
        next = 1

        state_table = []
        for m in range(10):
            li = []
            for i in range(2019):
                new_i = (i*10 + m) % 2019
                li.append(new_i)
            state_table.append(li)

        seed = int(s[0:4]) % 2019
        dic[current][seed] = 1

        for s_i in range(len_s-3):
            ans += dic[current][0]

            if s_i == len_s-4:
                break

            tgt = int(s[s_i+4])

            next_table = state_table[tgt]
            for i in range(2019):
                new_i = next_table[i]
                dic[next][new_i] = dic[current][i]
            seed = int(s[s_i+1:s_i+5]) % 2019
            dic[next][seed] += 1

            current, next = next, current

    print(ans)
    
# else:
    # do nothing

Submission status: Time Limit Exceeded

Solution code:
S=str(input())
n=len(S)
mod=2019
ans=0
box=[0 for i in range(n)]
T=[0 for i in range(n)]
T[-1]=int(S[-1])
box[-1]=1
for i in range(n-2,-1,-1):
    box[i]=box[i+1]*10%mod
    a=int(S[i])*box[i]+T[i+1]
    k=a%mod
    T[i]=k
T.append(0)
for i in range(mod):
    if i in T:
        m=T.count(i)
        ans+=m*(m-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = [0] * 2019
a[0] = 1
T = 0
r = 1
c = 0
for i in range(N-1, -1, -1):
    T = T + h[i] * r
    q = T % 2019
    r = r * 10
    c += a[q]
    a[q] += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
listS = list(str(S))
l = len(listS)
dp = int(listS[-1])
suml = [dp]
for i in range(l-1):
    dp = dp + pow(10,(i+1))*int(listS[-2-i])
    suml.append(dp % 2019)
mod = {0:1}
for a in suml:
    if a in mod.keys():
        mod[a] += 1
    else:
        mod[a] = 1
cnt = 0
for a in mod:
    if mod[a] > 1:
        cnt += (mod[a]*(mod[a]-1))//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int,list(input())))
n = len(s)

t = [0]*(n + 1)
mod = [0]*2019
mod[0] = 1
cnt = 0
for i in reversed(range(n)):
    t[i] = t[i+1] + s[i]*10**(n-i-1)
    mod[t[i]%2019] += 1
for m in mod:
    cnt += m*(m-1)//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = input()
mods = [0]*2019
mods[0] += 1
for i in range(len(s)):
    value = int(s[i:])
    # print(value)
    # print(value % 2019)
    # print('==========-')
    mods[value % 2019] += 1
ans = 0
for mod in mods:
    ans += (mod)*(mod-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  S_string = input()
  S_string += "0"
  dist = [0 for _ in range(2019)]

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

  ans = 0
  for xi in dist:
    ans += max(0, xi * (xi - 1) // 2)
  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*(10**(i-1))%2019)%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# a/b の切り上げ


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


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

    cnt = [0] * 2019
    # print(cnt)
    cnt[0] = 1
    ans = 0
    b = ''
    for c in s:
        b += c
        d = b[::-1]
        a = int(d)
        amari = a % 2019
        cnt[amari] += 1

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod])))

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
ss = []
nums = [(i+1)*2019 for i in range(200000//2019) if not "0" in str((i+1)*2019)]
for start in range(len(s)):
  end = start + 3
  while(end+1<=len(s)):
    if int(s[start:end+1]) in nums:
      cnt += 1
    end += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-(int(s[i-1])*(pow(10,n-i)))
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
for i in range(len(s)):
  r += s[-i-1]*(10**i)
  r %= 2019
  d[r] += 1
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*10**(i-1))%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = [0] * 2019
a[0] = 1
T = 0
r = 1
c = 0
for i in range(N-1, -1, -1):
    T = T + h[i] * r
    r = r * 10
    c += a[T%2019]
    a[T%2019] += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
s = input()
d = defaultdict(int)
d[0] = 1
for i in range(len(s))[::-1]: d[int(s[i:])%2019] += 1
ans = 0
for v in d.values():ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
d = [0 for _ in range(2019)]
for i in range(len(s)):
  r = int(s[i:])%2019
  d[r] += 1
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=[int(j) for j in input()][::-1]
m=len(s)
from collections import Counter
c=Counter()
tmp=0
c[0]+=1
t=1
for i in range(m):
    tmp+=t*s[i]
    c[tmp%2019]+=1
    t*=10
ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=j*(j-1)//2
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[0]*2019
mod[0]=1
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod])))

Submission status: Time Limit Exceeded

Solution code:
string=input()
length=len(string)
mod=[0]*2019
mod[0]=1
d=1
s=0
while length > 0:
  s+=int(string[length-1])*d
  mod[s%2019]+=1
  d*=10
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod])))

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
listS = list(str(S))
l = len(listS)
dp = int(listS[-1])
suml = [dp]
for i in range(l-1):
    dp = dp + (10**(i+1))*int(listS[-2-i])
    suml.append(dp % 2019)
mod = {0:1}
for a in suml:
    if a in mod.keys():
        mod[a] += 1
    else:
        mod[a] = 1
cnt = 0
for a in mod:
    if mod[a] > 1:
        cnt += (mod[a]*(mod[a]-1))//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=int(i*(i-1)/2)
  print(res)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
len_s = len(s)
pre,now = 0,0
mod = [0]*2019
mod[0]=1
for i in range(len_s):
    now = (10**i*int(s[len_s-i-1])+pre)%2019
    mod[now] += 1
    pre = now
sum_mod = 0
for m in mod:
    sum_mod += m*(m-1)//2
print(sum_mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0 for i in range(2019)]
d[0] = 1
tmp = 0
_10 = 1
# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    # print(int(s[i]), _10)
    tmp += (int(s[i]) * _10) % 2019
    _10 *= 10
    # print(tmp, tmp % 2019)
    d[tmp % 2019] += 1


# count = 0
# for i in range(len(d)):
#     if d[i] >= 2:
#         count += (d[i])*(d[i]-1)//2
# print(count)

# # print(dd)
print(sum(v*(v-1)//2 for v in d))

Submission status: Time Limit Exceeded

Solution code:
N = list(input())

n = len(N)

cnt = 0

for i in range(n-3):
     for j in range(n-i-3):
            joint = ''.join(N[i:n-j])  
            if int(joint)%2019 == 0:      
                 cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=[int(j) for j in input()][::-1]
m=len(s)
from collections import Counter
c=Counter()
tmp=0
c[0]+=1
for i in range(m):
    tmp+=pow(10,i)*s[i]
    c[tmp%2019]+=1
ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=j*(j-1)//2
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import collections
  s = list(map(int,input()))
  r = []
  x = 0
  for i in range(len(s)):
    x += s[-i-1]*(10**i)
    x %= 2019
    r.append(x)
  d = collections.Counter(r) 
  ans = 0
  if 0 in d:
    ans += d[0]
  for k,v in d.items():
    if v >= 2:
      ans += v*(v-1)//2
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0] * 2019
d[0] = 1
tmp = 0
_10 = 1
# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    tmp = tmp + (int(s[i]) * _10) % 2019
    _10 *= 10
    # print(tmp, tmp % 2019)
    d[tmp % 2019] += 1


# count = 0
# for i in range(len(d)):
#     if d[i] >= 2:
#         count += (d[i])*(d[i]-1)//2
# print(count)

# # print(dd)
print(sum(v*(v-1)//2 for v in d))

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = list(map(int, S))

r = 0
pow10 = 1
counter = [0] * 2019
counter[0] = 1
for i in range(1, len(S) + 1):
    r = (r + pow10 * S[-i]) % 2019
    counter[r] += 1
    pow10 *= 10

ans = 0
for count in counter:
    if count >= 2:
        ans += count * (count - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

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

res = 0
tmp = [0] * 2019
tmp[0] = 1
sum_of_digits = 0
d = 1

for c in S:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    # d %= 2019
    tmp[sum_of_digits] += 1

for t in tmp:
    res += (t * (t - 1)) // 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import Counter

    s=input()
    n=len(str(s))
    b=[]
    ans=0
    k=1
    for i in range(n):
        a = int(''.join([x.strip() for x in s[i:].split(',')]))
        b.append(a%2019)
    b.append(0)
    c = Counter(b)
    for i in list(c.values()):
        if i>=2:
            ans+=i*(i-1)/2
    print(int(ans))
resolve()

Submission status: Time Limit Exceeded

Solution code:
n=input()
length=len(n)
rs=0
for i in range(1,length-2):
    num=0
    start=0
    end=length-i
    for j in range(i):
        num=int(n[start+j:end+1+j])
        if num%2019==0:
            rs+=1
print(rs)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

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

  s=input()
  s=s.strip("\n")
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=int(i*(i-1)/2)
  print(res)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(S: str):

    l = [0] * 2019
    ps = 0
    d = 1
    for i in range(1, len(S) + 1):
        ps += int(S[-i]) * d
        l[ ps % 2019 ] += 1
        d *= 10

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

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
m=len(s)
from collections import Counter
c=Counter()
tmp=""
c[0]+=1
for i in s[::-1]:
    tmp=i+tmp
    c[int(tmp)%2019]+=1

ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=j*(j-1)//2
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1

    num = 0
    for digit, c in enumerate(S[::-1]):
        num += int(c) * 10 ** digit
        rem = num % 2019
        d[rem] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
ss = []
nums = [str((i+1)*2019) for i in range(200000//2019)]
for start in range(len(s)):
  end = start + 3
  while(end+1<=len(s)):
    ss.append(s[start:end+1])
    end += 1
for ss_ in ss:
  if ss_ in nums:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = list(map(int, input()))
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x += s*(10**i)
    d[x%2019] += 1
  ans = 0
  for m in d:
    ans += m*(m-1)//2
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=int(s)
m=len(s)
if n<2019:
    print(0)
    exit()
from collections import Counter
c=Counter()
tmp=""
c[0]+=1
for i in s[::-1]:
    tmp=i+tmp
    c[int(tmp)%2019]+=1

ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=j*(j-1)//2
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1])*pow(10,i))%p
	si[i] = sum(ai[:i+1])%p
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0] * 2019
d[0] = 1
tmp = 0
_10 = 1
# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    tmp = tmp + int(s[i]) * _10
    _10 *= 10
    # print(tmp, tmp % 2019)
    d[tmp % 2019] += 1


# count = 0
# for i in range(len(d)):
#     if d[i] >= 2:
#         count += (d[i])*(d[i]-1)//2
# print(count)

# # print(dd)
print(sum(v*(v-1)//2 for v in d))

Submission status: Time Limit Exceeded

Solution code:
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
tmp = ''
for i in range(N):
    tmp = S[i] + tmp
    cnt[i] = int(tmp)%2019
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n = (n+int(j)*10**i)%p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)