codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2193C.md (2032B)


      1 Source: https://codeforces.com/problemset/problem/2193/C
      2 
      3 C. Replace and Sum
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Today, KQ has an exam at the Grail Academy. A strict teacher gave a task that KQ could not solve. He was given two arrays $a$ and $b$ of length $n$. KQ is allowed to perform the following operations on the arrays:
     22 
     23 * Choose an index $i$ ($1\le i\lt n$) and replace $a_i$ with $a_{i+1}$.
     24 * Choose an index $i$ ($1\le i\le n$) and replace $a_i$ with $b_i$.
     25 
     26 Now he has $q$ queries. Each query is described by two numbers $l$ and $r$. His task is to find the maximum value of the sum $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ for each query, if he can perform any number of operations on any elements of the array. Since he is not skilled enough for this, he asks for your help.
     27 
     28 Input
     29 
     30 Each test consists of several test cases. The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.
     31 
     32 The first line of each test case contains two integers $n$, $q$ $(1\le n, q\le 2 \cdot 10^5)$.
     33 
     34 The second line of each test case contains $n$ integers $a_1, a_2,...,a_n$ $(1\le a_i\le 10^4)$.
     35 
     36 The third line of each test case contains $n$ integers $b_1, b_2,...,b_n$ $(1\le b_i\le 10^4)$.
     37 
     38 The following $q$ lines contain two integers $l$ and $r$ $(1\le l\le r\le n)$.
     39 
     40 It is guaranteed that the sum of the values of $n$ and the sum of the values of $q$ across all test cases do not exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, output $q$ numbers separated by spaces — the maximum values of the sums $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 3 1
     54 
     55 3 2 1
     56 
     57 1 2 3
     58 
     59 1 3
     60 
     61 1 1
     62 
     63 1
     64 
     65 2
     66 
     67 1 1
     68 
     69 3 2
     70 
     71 6 7 5
     72 
     73 9 6 8
     74 
     75 1 2
     76 
     77 2 3
     78 
     79 4 3
     80 
     81 4 3 2 1
     82 
     83 5 1 3 1
     84 
     85 1 2
     86 
     87 2 4
     88 
     89 3 4
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 9
     96 
     97 2
     98 
     99 17 16
    100 
    101 8 7 4
    102 ```
    103 
    104 Note
    105 
    106 Consider the first test case. Replace $a_3$ with $b_3$, $a = [3, 2, 3]$. Replace $a_2$ with $a_3$, $a = [3, 3, 3]$. The sum $a_1 + a_2 + a_3 = 9$.