beibarys.17's blog

Need Help
By beibarys.17, history, 6 years ago, In English

Hello Codeforces community!

Please help on this problem:

Given array with length N (1 ≤ N ≤ 105, 1 ≤ ai ≤ 109). And given Q queries(1 ≤ Q ≤ 105). For each query given one number X. (1 ≤ X ≤ 1014). Find number of subarrays which sum equals to X.

Sorry for my poor English.

  • Vote: I like it
  • +26
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

i think there is no solution less than o(n2), as there is about o(n2) possible subarrays to count their sum

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    The thing is, we don't have to enumerate subarrays to get their sum. If you want the actual subarrays, then we cannot have a solution that is better than O(n^2)

    → Reply