codeforces-scrape

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

2222B.md (3524B)


      1 Source: https://codeforces.com/problemset/problem/2222/B
      2 
      3 B. Artistic Balance Tree
      4 
      5 time limit per test
      6 
      7 1.5 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 After learning about the Artistic Balance Tree, Lizhous encountered the following problem.
     22 
     23 You are given an array $a$ consisting of $n$ integers. You need to perform exactly $m$ operations on $a$ in order. Each operation consists of two steps. Specifically, in the $i$-th operation, you are given an integer $x_i$, and you will:
     24 
     25 * First, select a center index $u$ and a non-negative length $y$ such that the interval $[u-y, u+y]$ lies entirely within $[1, n]$ (i.e., $u - y \ge 1$ and $u + y \le n$). For each $1\le i\le y$, swap the elements $a_{u-i}$ and $a_{u+i}$.
     26 * Then, mark the element at index $x_i$. If this element is already marked, nothing happens. Note that the marks are on elements, not indices. That means if an element is swapped with some other element by future operations, the mark will stay on it.
     27 
     28 After performing all $m$ operations, your task is to find the minimum possible sum of all elements that remain unmarked.
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     33 
     34 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the length of $a$ and the number of operations.
     35 
     36 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of $a$.
     37 
     38 The third line contains $m$ integers $x_1, x_2, \ldots, x_m$ ($1 \le x_i \le n$) — the indices to be marked in each operation.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     41 
     42 It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, output a single integer — the minimum possible sum of the unmarked elements after all operations.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 7 4
     56 
     57 1 2 3 4 5 6 7
     58 
     59 1 2 3 4
     60 
     61 7 4
     62 
     63 1 -2 3 4 -5 -6 -7
     64 
     65 7 6 5 4
     66 
     67 7 5
     68 
     69 21 -45 234 -8 423 12 -987
     70 
     71 6 6 6 6 6
     72 
     73 7 5
     74 
     75 -21 45 -234 8 -423 -12 987
     76 
     77 7 7 7 7 7
     78 
     79 7 3
     80 
     81 -1 2 -3 4 5 6 7
     82 
     83 1 2 3
     84 
     85 7 3
     86 
     87 -1 -2 -3 -4 -5 -6 -7
     88 
     89 1 2 3
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 6
     96 
     97 -20
     98 
     99 -362
    100 
    101 -637
    102 
    103 2
    104 
    105 -25
    106 ```
    107 
    108 Note
    109 
    110 In the first test case, one optimal operation sequence is as follows:
    111 
    112 1. Choose center $u=4$ and length $y=3$, and $a$ becomes $[7,6,5,4,3,2,1]$. Then, the element $a_1=7$ is marked.
    113 2. Choose center $u=1$ and length $y=0$, and $a$ remains $[7,6,5,4,3,2,1]$. Then, the element $a_2=6$ is marked.
    114 3. Choose center $u=1$ and length $y=0$, and $a$ remains $[7,6,5,4,3,2,1]$. Then, the element $a_3=5$ is marked.
    115 4. Choose center $u=1$ and length $y=0$, and $a$ remains $[7,6,5,4,3,2,1]$. Then, the element $a_4=4$ is marked.
    116 
    117 The unmarked elements are $1$, $2$, and $3$, and the answer is $1+2+3=6$.
    118 
    119 In the second test case, one optimal operation sequence is as follows:
    120 
    121 1. Choose center $u=4$ and length $y=3$, and $a$ becomes $[-7,-6,-5,4,3,-2,1]$. Then, the element $a_7=1$ is marked.
    122 2. Choose center $u=5$ and length $y=1$, and $a$ becomes $[-7,-6,-5,-2,3,4,1]$. Then, the element $a_6=4$ is marked.
    123 3. Choose center $u=1$ and length $y=0$, and $a$ remains $[-7,-6,-5,-2,3,4,1]$. Then, the element $a_5=3$ is marked.
    124 4. Choose center $u=5$ and length $y=1$, and $a$ becomes $[-7,-6,-5,4,3,-2,1]$. Then, the element $a_4=4$ is marked.
    125 
    126 The unmarked elements are $-2$, $-5$, $-6$, and $-7$, and the answer is $(-2)+(-5)+(-6)+(-7)=-20$.