codeforces-scrape

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

2151C.md (3205B)


      1 Source: https://codeforces.com/problemset/problem/2151/C
      2 
      3 C. Incremental Stay
      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 [Danimal Cannon, Zef - The Lunar Whale](https://soundcloud.com/danimalcannon/the-lunar-whale)
     22 
     23 ⠀
     24 
     25 You are the security guard of a museum.
     26 
     27 The main door of the museum is both an entrance and an exit. At most one person can pass through the door every second. There is a sensor that detects when a visitor passes through the door. The sensor cannot determine neither who the visitor is, nor whether he entered or exited the museum. The sensor detected some activity in $2n$ distinct moments of time $a_1, a_2, \ldots, a_{2n}$ (measured in seconds).
     28 
     29 For each visitor, his stay time is equal to the exit time minus the entrance time.
     30 
     31 Right now the museum is closed (so it has no visitors), and you wonder about the maximum possible total stay time today, i.e., the maximum possible sum of the stay times of all the visitors that entered the museum today. At second $0$, the museum was closed as well.
     32 
     33 For security reasons, there is also a limit on the number of people who can stay in the museum simultaneously, but you forgot this limit. For each $k$ from $1$ to $n$, you want to determine the maximum possible total stay time today, assuming that at most $k$ people can stay in the museum simultaneously.
     34 
     35 Input
     36 
     37 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.
     38 
     39 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), indicating that the sensor detected some activity in $2n$ distinct moments of time.
     40 
     41 The second line of each test case contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \leq a_1 \lt a_2 \lt \ldots \lt a_{2n} \leq 10^9$) — the seconds when the sensor detected some activity.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print $n$ integers: for each $k$ from $1$ to $n$, print the maximum possible total stay time today, assuming that at most $k$ people can stay in the museum simultaneously.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 1
     57 
     58 32 78
     59 
     60 2
     61 
     62 4 5 6 9
     63 
     64 4
     65 
     66 6149048 26582657 36124499 43993239 813829899 860114890 910238130 913669539
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 46
     73 
     74 4 6
     75 
     76 78018749 1737022233 1845329695 3385003015
     77 ```
     78 
     79 Note
     80 
     81 In the first test case, the sensor detected activity at seconds $32$ and $78$. Recall that $k$ is the maximum number of people who can stay in the museum simultaneously.
     82 
     83 * If $k$ is $1$, the maximum possible total stay time is $46$, reached if visitor $1$ enters at time $32$ and exits at time $78$.
     84 
     85 In the second test case, the sensor detected activity at seconds $4$, $5$, $6$, and $9$.
     86 
     87 * If $k$ is $1$, the maximum possible total stay time is $4$, reached if visitor $1$ enters at time $4$ and exits at time $5$, and visitor $2$ enters at time $6$ and exits at time $9$.
     88 * If $k$ is $2$, the maximum possible total stay time is $6$, reached if visitor $1$ enters at time $4$ and exits at time $9$, and visitor $2$ enters at time $5$ and exits at time $6$.