codeforces-scrape

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

1857E.md (2356B)


      1 Source: https://codeforces.com/problemset/problem/1857/E
      2 
      3 E. Power of Points
      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 You are given $n$ points with integer coordinates $x_1,\dots x_n$, which lie on a number line.
     22 
     23 For some integer $s$, we construct segments [$s,x_1$], [$s,x_2$], $\dots$, [$s,x_n$]. Note that if $x_i \lt s$, then the segment will look like [$x_i,s$]. The segment [$a, b$] covers all integer points $a, a+1, a+2, \dots, b$.
     24 
     25 We define the power of a point $p$ as the number of segments that intersect the point with coordinate $p$, denoted as $f_p$.
     26 
     27 Your task is to compute $\sum\limits_{p=1}^{10^9}f_p$ for each $s \in \{x_1,\dots,x_n\}$, i.e., the sum of $f_p$ for all integer points from $1$ to $10^9$.
     28 
     29 For example, if the initial coordinates are $[1,2,5,7,1]$ and we choose $s=5$, then the segments will be: $[1,5]$,$[2,5]$,$[5,5]$,$[5,7]$,$[1,5]$. And the powers of the points will be: $f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$. Their sum is $2+3+3+3+5+1+1=18$.
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of points.
     36 
     37 The second line contains $n$ integers $x_1,x_2 \dots x_n$ ($1 \le x_i \le 10^9$) — the coordinates of the points.
     38 
     39 It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2\cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output $n$ integers, where the $i$-th integer is equal to the sum of the powers of all points for $s=x_i$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 
     52 3
     53 
     54 1 4 3
     55 
     56 5
     57 
     58 1 2 5 7 1
     59 
     60 4
     61 
     62 1 10 100 1000
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 8 7 6
     69 16 15 18 24 16
     70 1111 1093 1093 2893
     71 ```
     72 
     73 Note
     74 
     75 In the first test case we first choose $s=x_1=1$, then the following segments are formed: $[1,1]$,$[1,4]$,$[1,3]$.
     76 
     77 The powers of the points will be as follows: $f_1=3, f_2=2, f_3=2, f_4=1, f_5=0 \dots$ The sum of powers of the points: $3+2+2+1+0+\dots+0=8$.
     78 
     79 After that we choose $s=x_2=4$. Then there will be such segments: $[1,4]$,$[4,4]$,$[3,4]$, and powers of the points are $f_1=1, f_2=1, f_3=2, f_4=3$.
     80 
     81 At the end we take $s=x_3=3$ and the segments look like this: $[1,3]$,$[3,4]$,$[3,3]$, the powers of the points are $f_1=1, f_2=1, f_3=3, f_4=1$.