Intervals and Intersections

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME72/hindi/IAI.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME72/bengali/IAI.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME72/mandarin/IAI.pdf), [Russian](http://www.codechef.com/download/translated/LTIME72/russian/IAI.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME72/vietnamese/IAI.pdf) as well. Vivek believes that this problem is the hardest problem ever and no one can solve it. Please prove him wrong. You are given a sequence $A_1, A_2, \ldots, A_N$ and $M$ intervals $[L_1, R_1], [L_2, R_2], \ldots, [L_M, R_M]$. For any subset $S$ of these intervals:  If $S$ is nonempty, let's define $L = \mathrm{max}_{i \in S}\,(L_i)$ and $R = \mathrm{min}_{i \in S}\,(R_i)$.  The set $S$ is *disjoint* if $S$ is empty or $L \gt R$. Otherwise, the intersection of the intervals from this set is the interval $[L, R]$.  If $S$ is not disjoint, its value is $\sum_{j=L}^{R} (jL+1) \cdot A_j$. Find the maximum of values of all nondisjoint subsets of the given intervals. ### 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 $M$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  $M$ lines follow. For each $i$ ($1 \le i \le M$), the $i$th of these lines contains two spaceseparated integers $L_i$ and $R_i$. ### Output For each test case, print a single line containing one integer ― the maximum value of a nondisjoint subset. ### Constraints  $1 \le T \le 5$  $1 \le N \le 10^5$  $1 \le M \le 5 \cdot 10^4$  $A_i \le 10^6$ for each valid $i$  $1 \le L \le R \le N$ ### Subtasks **Subtask #1 (30 points):** $1 \le M \le 3 \cdot 10^3$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 2 3 2 2 1 2 1 2 2 3 3 2 2 3 4 1 2 2 3 ``` ### Example Output ``` 1 11 ``` ### Explanation **Example case 1:** It is optimal to choose the intervals $[1, 2]$ and $[2, 3]$. Their intersection is the interval $[2, 2]$ (so the set of these two intervals is not disjoint) and its value is $A_2 \cdot 1 = 1$.Author:  vivek_1998299 
Tags  convexhulltrick, ltime72, mediumhard, prefixsum, segmenttree, taran_1407, vivek_1998299 
Date Added:  17052019 
Time Limit:  4 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