Firdavs and Planet F

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME71/hindi/FAPF.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME71/bengali/FAPF.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME71/mandarin/FAPF.pdf), [Russian](http://www.codechef.com/download/translated/LTIME71/russian/FAPF.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME71/vietnamese/FAPF.pdf) as well. Firdavs is living on planet F. There are $N$ cities (numbered $1$ through $N$) on this planet; let's denote the value of city $i$ by $v_i$. Firdavs can travel directly from each city to any other city. When he travels directly from city $x$ to city $y$, he needs to pay $f(x, y) = v_yv_x+yx$ coins (this number can be negative, in which case he receives $f(x, y)$ coins). Let's define a simple path from city $x$ to city $y$ with length $k \ge 1$ as a sequence of cities $a_1, a_2, \ldots, a_k$ such that all cities in this sequence are different, $a_1 = x$ and $a_k = y$. The cost of such a path is $\sum_{i=1}^{k1} f(a_i, a_{i+1})$. You need to answer some queries for Firdavs. In each query, you are given two cities $x$ and $y$, and you need to find the minimum cost of a simple path from city $x$ to city $y$. Then, you need to find the length of the longest simple path from $x$ to $y$ with this cost. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $v_1, v_2, \ldots, v_N$.  The following $Q$ lines describe queries. Each of these lines contains two spaceseparated integers $x$ and $y$. ### Output For each query, print a single line containing two spaceseparated integers ― the minimum cost and the maximum length. ### Constraints  $1 \le T \le 100$  $1 \le N, Q \le 2 \cdot 10^5$  $0 \le v_i \le 10^9$ for each valid $i$  $1 \le x, y \le N$  the sum of $N$ in all test cases does not exceed $5 \cdot 10^5$  the sum of $Q$ in all test cases does not exceed $5 \cdot 10^5$ ### Subtasks **Subtask #1 (30 points):**  $1 \le N, Q \le 1,000$  $v_1 \lt v_2 \lt \ldots \lt v_N$  the sum of $N$ in all test cases does not exceed $5,000$  the sum of $Q$ in all test cases does not exceed $5,000$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 2 4 2 4 2 5 7 2 3 3 4 2 1 1 1 2 1 ``` ### Example Output ``` 4 3 3 2 1 2 ``` ### Explanation **Example case 1:** For the first query, there are two paths with cost $4$ from city $2$ to city $3$:  $2 \rightarrow 1 \rightarrow 3$: cost $(42+12)+(54+31) = 4$, length $3$  $2 \rightarrow 3$: cost $52+32 = 4$, length $2$ All other paths have greater costs, so the minimum cost is $4$. Among these two paths, we want the one with greater length, which is $3$.Author:  farhod_farmon 
Editorial  https://discuss.codechef.com/problems/FAPF 
Tags  easy, farhod_farmon, ltime71, observations, partialsums, taran_1407 
Date Added:  25042019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions