 # DCP-19: Multiplication Interval Back to All Problems

Hard Data Structures > Segment Tree/Interval Tree

Software Engineering requires knowledge about algorithms, data structures, design pattern, UML diagram, software development approach. The main focus of all this knowledge is to make the software more efficient, robust and workable. Because if you develop a software which does something slower than human, then what is the point of building that software? Below, there is a problem which can be done with simple looping to all the elements of the array for each query, but that is not efficient, can you make it efficient? Given an array with **N** elements, indexed from **1** to **N**. Now you will be given some queries in the form **I J**, your task is to find the minimum multiplication value of all possible interval between index **I** to **J**, and also for that multiplication value you need to find the longest interval. Lets say we have an array A size 5, indexed from 1 to 5. Now the multiplication value of the interval [1,3] = A*A*A Input: ------ Input starts with an integer **T (≤ 5)**, denoting the number of test cases. The first line of a case is a blank line. The next line contains two integers **N (1 ≤ N ≤ 10^5), q (1 ≤ q ≤ 10^5)**. The next line contains **N** space separated integers forming the array. There integers range in **[0, 10^5]**. The next **q** lines will contain a query which is in the form **I J (1 ≤ I ≤ J ≤ N)**. Output: ------- For each test case, print the case number in a single line. Then for each query you have to print a line containing three numbers, first one is the minimum multiplication value of all possible interval between index **I** to **J**, second and third number will point to the start index and end index of the interval which is longest interval between index **I** to **J** having the minimum multiplication value. If there are multiple intervals having the minimum multiplication value as well as the longest then print the interval which starts earlier. See the output section for further understanding Sample Input ------------ 2 5 3 2 22 10 12 2 2 4 4 5 1 5 2 1 10 10 1 2 Sample Output ------------- Case 1: 10 3 3 2 5 5 2 1 1 Case 2: 10 1 1 **Notes** For the first test case, for query 2, 4, these intervals are possible: [2,2] = 22 [2,3] = 22 * 10 = 220 [2,4] = 22 * 10 * 12 = 2640 [3,3] = 10 [3,4] = 10 * 12 = 120 [4,4] = 12 Among all of these intervals, [3,3] interval have the minimum multiplication value. For the Second test case first query [1,2] we have two longest intervals with minimum multiplication value [1,1], [2,2]. So print [1,1] as it starts earlier.

### Problem Limits

 Language Time Limit (seconds) C 2.00 C++ 2.00 C++14 2.00 C# 4.00 Go 4.00 Java 4.00 JavaScript 4.00 Objective-C 4.00 Perl 4.00 PHP 4.00 Python 4.00 Python3 4.00 Ruby 4.00 VB.Net 4.00

# 33/230

Solve/Submission

### Ranking

# User Language Timing
01 GustavoCandido Cpp14 0.27s
02 Morass Cpp14 0.32s
03 frochbg Cpp14 0.36s
04 feodorv C 0.36s
05 Sarwar05 Cpp 0.40s
06 THOOR_001 Cpp 0.42s
07 tariqiitju Cpp14 0.43s
08 Robbinb1993 Cpp14 0.46s
09 Masum_ice Cpp14 0.53s
10 _GhOstMan_ Cpp14 0.54s
11 seyedssz Cpp14 0.61s
12 moshiur_cse15 Cpp14 0.63s
13 jalal Cpp 0.65s
14 ovis96 Cpp14 0.83s
15 skmonir Cpp14 0.85s
16 wellidk Cpp14 0.87s
17 _dipu Cpp14 1.01s
18 fresco_ferdini Cpp14 1.02s
19 Hasinur_ Cpp14 1.52s
20 nasif2587 Cpp14 1.63s
Feedback