Problem: 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.

Submission attempts (in order):
from sys import stdin
#import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

aa_table = [0 for i in range(2019)]
aa_table2 = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table2[res_map[i]]+=1

aa_table2[0]+=1


for i in range(1,N):
    if res_map[i]<res_map[i-1]:
        aa = 2/0

for i in range(1,len(res_map)):
    if temp_num==int(res_map[i]):
        index+=1
        continue
    else:
        aa_table[temp_num] = index
        index=1
        temp_num=int(res_map[i])

aa_table[0] += 1 

for i in range(2018):
    if aa_table[i] != aa_table2[i]:
        aa = 2/0
#        if temp_num==0:

#        elif index>1:

#        index=1
#        temp_num=int(res_map[i])


tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)






#        num+=1

    

print(tot)



from sys import stdin
#import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

aa_table = [0 for i in range(2019)]
aa_table2 = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table2[res_map[i]]+=1

aa_table2[0]+=1


for i in range(1,N):
    if res_map[i]<res_map[i-1]:
        aa = 2/0

for i in range(1,len(res_map)):
    if temp_num==int(res_map[i]):
        index+=1
        if i==len(res_map)-1:
            aa_table[temp_num]=index
        continue
    else:
        aa_table[temp_num] = index
        index=1
        temp_num=int(res_map[i])
        if i==len(res_map)-1:
            aa_table[temp_num]=1

aa_table[0] += 1 


tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)






#        num+=1

    

print(tot)



Verdicts: Runtime Error

Accepted