PROBLEM LINK:
Author: Ranjan Kumar Singh
Tester: Sudipto Roy
Editorialist: Ved Prakash
DIFFICULTY:
EASY
PROBLEM:
Chef is distributing his u varieties of chocolates among N students in a line.
He ditributes kp amount of chocolate of variety up to the students from position i to j.
Now after distribution of chocolates, we have m queries to calculate the no. of choclates to student at position mi.
EXPLANATION:
We need to update the no. of chocolate to student at position i by clever means.
Let the u updatation steps be like:
The no. of chocolate
at starting position as choc[i]=choc[i]+k and
at ending position as choc[j+1]=choc[j+1]-k
After this, to get the number of chocolate at position i, update the array choc[i] as summation of all choc[a] (0<=a<=i)
Pseudo Code:
for a=0 to N
choc[a]=0; //initialisation//
for a=0 to u
{
scan i,j,k
choc[i]=choc[i]+k; //updatation at starting position//
choc[j+1]=choc[j+1]-k; //updatation at end position//
}
for a=0 to N
{
sum=sum+choc[a];
number_of_chocolate_at[a]=sum; //final updation for the number of chocolate at position i//
}
Complexity: O(u+N+m).