GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 26 October 2022

[Solution] Final Sum CodeChef Solution | Solution CodeChef



Problem

Chef has an array A of length N. In one operation, Chef can:

  • Choose any subarray [L, R] (1 \leq L \leq R \leq N);
  • Add 1 to A_L, subtract 1 from A_{L+1}, add 1 to A_{L+2}, subtract 1 from A_{L+3} and so on, till A_R.

Chef performed Q such operations where the i^{th} operation was performed on the subarray [L_i, R_i].

Determine the final sum of the array after these Q operations.

Note that a subarray is formed by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two integers N, Q, number of elements and the number of queries.
    • The next line contains N space-separated integers A_1, A_2, \dots A_N - denoting the array A.
    • The next Q lines contains two space-separated integers with i^{th} line containing L_i, R_i.

Output Format

For each test case, output the final sum of the array after performing all the Q operations.

Explanation:

Test case 1: The queries are as follows:

  • Query 1: The chosen subarray is [1, 3, 4, 4, 2] which changes to [1+1, 3-1, 4+1, 4-1, 2+1] = [2, 2, 5, 3, 3]. Thus, the array becomes [2, 2, 5, 3, 3].
  • Query 2: The chosen subarray is [5, 3] which changes to [5+1, 3-1] = [6, 2]. Thus, the array becomes [2, 2, 6, 2, 3].
  • Query 3: The chosen subarray is [2] which changes to [2+1] = [3]. Thus, the array becomes [2, 3, 6, 2, 3].

The sum of final array is 2+3+6+2+3 = 16.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

Test case 2: The queries are as follows:

  • Query 1: The chosen subarray is [4] which changes to [4+1] = [5]. Thus, the array becomes [5].
  • Query 2: The chosen subarray is [5] which changes to [5+1] = [6]. Thus, the array becomes [6].

The sum of final array is 6.

No comments:

Post a Comment