Problem Statement (from HackerRank)
We have two arrays \$a\$ and \$b\$ of length \$N\$, initially all values equals to zero. We have \$Q\$ operations. Let's define three types of operations on this arrays:
1 l r c
: Increase \$a_l, a_{l+1}, \ldots, a_r\$ by \$c\$.2 l r c
: Increase \$b_l, b_{l+1}, \ldots, b_r\$ by \$c\$.3 l r
: Print \$a_l\cdot b_l + a_{l+1}\cdot b_{l+1} +\ldots+ a_r\cdot b_r\$ in modulo \$1000000007\$.Input Format
First line of the input consists of \$N\$ and \$Q\$. Next \$Q\$ lines contain one of the three types of operations.
Constraints
- \$1 \le N \le 10^9\$
- \$1 \le Q \le 200000\$
- \$1 \le c \le 10000\$
- \$1 \le l \le r \le N\$
Output Format
Whenever you get a type 3 operation, you should print the answer in a new line.
Sample Input 1
5 3 1 1 5 5 2 2 4 2 3 3 4
Sample Output 1
20
Sample Input 2
10 20 1 9 9 6768 2 5 5 2202 3 7 7 2 3 9 1167 2 1 7 8465 3 1 5 2 1 1 1860 3 9 9 2 5 5 2153 1 5 7 749 3 1 1 2 8 10 3129 3 1 1 1 2 10 2712 2 1 8 79 1 1 6 4645 1 7 7 1358 3 2 10 1 9 9 8677 3 8 10
Sample Output 2
0 0 7898256 0 0 506356461 98353320
How can I efficiently store and process data for this problem?
#include<stdio.h>
#include<string.h>
int main()
{
long n,q,ch,l,r,c,i,j;
/* n, q, l, r, c works as per problem statement.
ch is used to scan the first digit of operation.
i and j are used to control the loops. */
scanf("%ld %ld",&n,&q);
long a[n],b[n];
memset(&a, 0, sizeof a);
memset(&b, 0, sizeof b);
for(i=0;i<n;i++) //Init to 0
{
a[i]=0;
b[i]=0;
}
for(i=0;i<q;i++)
{
scanf("%ld ",&ch); //Look for the first digit
switch(ch)
{
case 1:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(j=l;j<r;j++)
a[j]+=c; //Adds c to every element of a
break;
case 2:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(j=l;j<r;j++)
b[j]+=c; //Adds c to every element of b
break;
case 3:
scanf("%ld %ld",&l,&r);
l--;
c=0;
for(j=l;j<r;j++)
c+=a[j]*b[j]; //Adds the product
printf("%ld\n",c%1000000007); //Prints the value after using mod
break;
}
}
}