We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

intmain(){longlongintn,k,i,max=0,x=0;scanf("%lld %lld",&n,&k);int*a=(int*)malloc(sizeof(int)*(n+1));for(i=0;i<n;i++){*(a+i)=0;}for(i=0;i<k;i++){longlongintc,d,g;scanf("%lld %lld %lld",&c,&d,&g);*(a+c)+=g;if(d+1<=n){*(a+d+1)-=g;}}for(i=1;i<=n;i++){x+=*(a+i);if(max<x){max=x;}}printf("%lld",max);/* Enter your code here. Read input from STDIN. Print output to STDOUT */return0;}

Edit 1: I had used pointers so much because I was learning about pointers at that time

Edit 2: Many were asking about the logic, I will try to give you the intuition
The basic idea is doing lazy update,i.e., not doing actual update of range every time and instead store the net update somwhere so that it can be easily done in one go

Suppose we have an array 3,2,4,5,7,9,4 and we want to make update, from 0 to 2 increase value by 1
We create update arr of equal size filled with 0 . For first update, update[0]+=1 and update[3]-=1. We add where the interval begins, we subtract just after the interval ends which just helps in excluding all indices from 3 and after that from being incremented. How so? When we have to do final update, we actually sum values from left. After suming values from left(update[i]+=update[i-1]) and filling update array you would get, update = [1,1,1,0,0,0,0]. Notice that we succesfully excluded all indices from 3 and after. If we hadn't subtracted at position 3, the whole update array would have been filled with 1. Similarly we can make more range updates using same logic. Sum at each index gives the net value to be updated. Hope this helps!

## Array Manipulation

You are viewing a single comment's thread. Return to all comments →

Same solution in C

Edit 1: I had used pointers so much because I was learning about pointers at that timeEdit 2:Many were asking about the logic, I will try to give you the intuition The basic idea is doing lazy update,i.e., not doing actual update of range every time and instead store the net update somwhere so that it can be easily done in one goSuppose we have an array 3,2,4,5,7,9,4 and we want to make update, from 0 to 2 increase value by 1 We create update arr of equal size filled with 0 . For first update,

`update[0]+=1`

and`update[3]-=1`

. We add where the interval begins, we subtract just after the interval ends which just helps in excluding all indices from 3 and after that from being incremented. How so? When we have to do final update, we actually sum values from left. After suming values from left(`update[i]+=update[i-1]`

) and filling update array you would get,`update = [1,1,1,0,0,0,0]`

. Notice that we succesfully excluded all indices from 3 and after. If we hadn't subtracted at position 3, the whole update array would have been filled with 1. Similarly we can make more range updates using same logic. Sum at each index gives the net value to be updated. Hope this helps!