kritipandey's blog

(Appeared in Walmart CodeHers around 13 June )
By kritipandey, history, 3 years ago, In English
  • You are given an array A of size N. Initially all the elements of the array are zero. Also, you have an infinite length array S which holds the property that the index is equal to the value of the array i.e. for each i(i>=1),S[i]=i.
  • Now you have Q queries to perform on array A. Each query contains two variables L and R.
  • For each query you have to perform the following operations:
  • For all index i, where L<=i<=R you have to add the value of the array S from starting position incrementing its positions to the array element at index i. That is:
  • initialize j=1;
  • for each i=L to R:
  • A[i]=A[i]+S[j]
  • j=j+1
  • After performing Q queries, you need to output the final values present in array A
  • INPUT FORMAT:
  • First line contains integer N indicating the size of the array indexed from 1 to N.
  • Second line contains integer Q indicating no of Queries.
  • Followed by Queries where each line contains two no L and R.
  • 1<=N<=100000
  • 1<=Q<=100000
  • 1<=L<=R<=N
  • Output Format:
  • Print output of final values present in array A in a space separated order
  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Please provide the link to the question. Otherwise how can it be checked if it is from a ongoing test.

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Create a new array $$$C$$$, for each query $$$(L, R)$$$, add $$$1$$$ to $$$C[L]$$$, add $$$L-R-2$$$ to $$$C[R+1]$$$ and $$$R-L+1$$$ to $$$C[R+2]$$$. At the end $$$A=prefixsum(prefixsum(C))$$$

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

*walmart chut quota hiring

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Put your toxicity in your dick. Don't ruin the decoram of codeforces.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
      Really sorry bro and the codeforces community also I want to say tha
      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this part of the interview process in order to become a Walmart employee?

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I am not really sure but this question was asked in Byterace by IIT Patna in Codechef , You can check here Problem Link This is a classic Prefix Sum problem

→ Reply