shorbot's blog

Need Help with Prefix Sum — 816B Karen and Coffee
By shorbot, history, 4 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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<n;i++) { cin >> 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; }

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

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<n;i++) {
        cin >> 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/

→ Reply