GUPTA MECHANICAL

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

Thursday 4 August 2022

[Solution] Swap and Maximum Block Codeforces Solution



E. Swap and Maximum Block
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array of length 2n. The elements of the array are numbered from 1 to 2n.

You have to process q queries to this array. In the i-th query, you will be given an integer k (0kn1). To process the query, you should do the following:

  • for every i[1,2n2k] in ascending order, do the following: if the i-th element was already swapped with some other element during this query, skip it; otherwise, swap ai and ai+2k;
  • after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment).

For example, if the array a is [3,5,3,2,8,20,6,1],

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 and k=1, the query is processed as follows:

  • the 1-st element wasn't swapped yet, so we swap it with the 3-rd element;
  • the 2-nd element wasn't swapped yet, so we swap it with the 4-th element;
  • the 3-rd element was swapped already;
  • the 4-th element was swapped already;
  • the 5-th element wasn't swapped yet, so we swap it with the 7-th element;
  • the 6-th element wasn't swapped yet, so we swap it with the 8-th element.

So, the array becomes [3,2,3,5,6,1,8,20]. The subsegment with the maximum sum is [5,6,1,8], and the answer to the query is 18.

Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.

Input

The first line contains one integer n (1n18).

The second line contains 2n integers a1,a2,,a2n (109ai109).

The third line contains one integer q (1q2105).

Then q lines follow, the i-th of them contains one integer k (0kn1) describing the i-th query.

Output

For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.

No comments:

Post a Comment