• + 13 comments

    Same solution in C

    int main() {
        long long int n,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++){
            long long int c,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 */
        return 0;
    }
    

    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!