Challenge 1You are given a one dimensional integer array A of length N. You need to maintain the array under Q queries of the following four types.
Query 1 : 1 x y v This implies adding v to array A to all the indices from x to y, i.e.,
for (i = x; i <= y; i++)
Ai += v;
Query 2 : 2 x y v This implies multiplying the scalar v with the array A for all the indices from x to y, i.e.,
for (i = x; i <= y; i++)
Ai *= v
Query 3 : 3 x y v This implies initializing the array A at all the indices from x to y with the value v, i.e.,
for (i = x; i <= y; i++)
Ai = v
Query 4 : 4 x yThis is a report query which needs to find the sum of the values in A from x to y, i.e.,
sum = 0;
for (i = x; i <= y; i++)
sum += Ai
sum %= M
Output sum.Note: a%b represents the remainder of a when divided by b.
Input[size=78%]First line contains two space separated integers N, Q.[/size]Next line contains N space separated integers denoting the array A.
Next Q lines contain queries which can be of any of the above four types.
OutputPrint array elements separated with space after each operation. In case of Query 4 type, print since integer as result of it.
PointsAll type of Queries in program : 50 Points
Any three Queries in program: 35 Points
Any two Queries in program: 20 points
One query in program:8 Points
ExampleInput:4 4
1 2 3 4
4 1 4
Output:Time Before algo => ....
10
Time after algo => ....ExplanationInitial A : [1, 2, 3, 4]
Result of first query : 1 + 2 + 3 + 4 = 10
You have to print time in milliseconds for each query. For example if i enter Query 1 on my array then you will first print time in milliseconds after that do your algo and after printing result of query you have to again print time of that moment in millisecondsuse this to print time in milliseconds in C++11Only registered users can see contents. Please click here to Register or Login.
and includeOnly registered users can see contents. Please click here to Register or Login.
Languages accepted : Java,PHP,C,C++