### shorbot's blog

By shorbot, history, 3 weeks ago, ,

Actually im learning prefix sum and trying to solve problems with it. Im trying this problem for a quite long time. I dont no why my code is not showing the right output. Can someone help? Thanks in advance. 87009522

• -8

 » 3 weeks ago, # |   -7 I first read it as Coffee with Karan XD
•  » » 3 weeks ago, # ^ |   0 haha
 » 3 weeks ago, # | ← Rev. 2 →   +1 u are using the same variable i in the nested loop(look at below code),u should replace it by j or something. And even doing so will result in TLE.for(int i=0;i> srt >> en; mi=min(mi,srt); mx=max(mx,en); for(int i=srt;i<=en;i++){ arr[i]++; } }Also u are putting 2 instead of k.for(int i=mi;i<=mx;i++){ if(arr[i]>=2)ans[i]=++c; else ans[i]=c; }
 » 3 weeks ago, # |   0 In this line: if(arr[i]>=2)ans[i]=++c; I think you mean to put k instead of 2. Also your algorithm is O(n^2) due to this part: for(int i=0;i> srt >> en; mi=min(mi,srt); mx=max(mx,en); for(int i=srt;i<=en;i++){ arr[i]++; } } But you can easily improve it to $O(n)$ by using a difference array. You can read about it here: https://cses.fi/book/book.pdf and/or here: https://www.geeksforgeeks.org/difference-array-range-update-query-o1/