1
\$\begingroup\$

Input: The first line of input consists of two integers n and q. Here, 1 ≤ n ≤ 86,400 is the number of seconds your call center is open for each day and 1 ≤ q ≤ 50,000 is the number of queries you want to make.

The next line contains n integers, each between 0 and 100. Consecutive integers will be separated by a single space. The ith integer on this line indicates how many new calls were received by your call center yesterday in the ith second of operation. Finally, q lines follow. Each consists of two integers 1 ≤ s ≤ t ≤ n separated by a single space.

Output: consists of q lines, one for each query. For each query with integers s, t, you should output the total number of calls your call center received yesterday between the sth and tth second of operation (including the calls received exactly at second s and at second t).

Sample Input 1
13 7
5 3 13 0 0 1 4 3 12 1 0 0 17 
1 3 
1 4 
1 13 
3 3 
4 4 
2 7
8 11

Sample Output 1
21
21
59
13
0
21
16

The code I made is not fast enough. What can I do to make it faster? Any suggestions would help, and any explanation as to why this is not fast and anything that would make it faster.

Here is a GitHub repository with the test center.

# read the first line
n , q = list(map(int, input().split()))
# read the calls
calls = [int(i) for i in input().split()]
s_array , t_array = [], []
# read and process each query
for i in (range(0,q)):
    s , t = list(map(int, input().split()))
    s_array.append(s)
    t_array.append(t)

#print  the answer
sorting = {} #empty dictionary
#how many quaries between eacth s and t array
for i in range(0, q):
    sorting[i] = sum(calls[s_array[i] - 1:t_array[i]])

for k, v in sorting.items():
   print(v)

Edit: answer figured out:

# read the first line
n, q = list(map(int, input().split()))

# read the calls
calls = [int(i) for i in input().split()]

s_array, t_array = [], []
# read and process each query
for i in (range(0, q)):
    s, t = list(map(int, input().split()))
    s_array.append(s)
    t_array.append(t)

aux = [i for i in range(0, n)]  # initializing theauxiliary array
aux[0] = calls[0]

for i in range(1, n):
    # O(n) time to find the sum till that index and store in auxiliary array
    aux[i] = aux[i-1] + calls[i]

# print the answer
sorting = {}  # empty dictionary
# how many quaries between eacth s and t array
for i in range(0, q):
    sorting[i] = aux[t_array[i]-1]-aux[s_array[i]-1]+calls[s_array[i]-1]
    # sum(i,j) = aux[j] - aux[i-1]; =>Constant time

for k, v in sorting.items():
    print(v)
\$\endgroup\$
  • \$\begingroup\$ Regarding your Rev 6: if you would like your new code to be reviewed, you can just delete the original code. If you don't want your new code to be reviewed, you can roll back the question to Rev 5, and post your new code as an answer (but you need to include an explanation of what you changed and why, else it's not a valid answer). Alternatively, you can just delete your question if you are no longer interested in a review. \$\endgroup\$ – 200_success Mar 7 '18 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.