codeforces-scrape

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

1166C.md (2981B)


      1 Source: https://codeforces.com/problemset/problem/1166/C
      2 
      3 C. A Tale of Two Lands
      4 
      5 time limit per test
      6 
      7 1 second
      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 The legend of the foundation of Vectorland talks of two integers $x$ and $y$. Centuries ago, the array king placed two markers at points $|x|$ and $|y|$ on the number line and conquered all the land in between (including the endpoints), which he declared to be Arrayland. Many years later, the vector king placed markers at points $|x - y|$ and $|x + y|$ and conquered all the land in between (including the endpoints), which he declared to be Vectorland. He did so in such a way that the land of Arrayland was completely inside (including the endpoints) the land of Vectorland.
     22 
     23 Here $|z|$ denotes the absolute value of $z$.
     24 
     25 Now, Jose is stuck on a question of his history exam: "What are the values of $x$ and $y$?" Jose doesn't know the answer, but he believes he has narrowed the possible answers down to $n$ integers $a_1, a_2, \dots, a_n$. Now, he wants to know the number of unordered pairs formed by two different elements from these $n$ integers such that the legend could be true if $x$ and $y$ were equal to these two values. Note that it is possible that Jose is wrong, and that no pairs could possibly make the legend true.
     26 
     27 Input
     28 
     29 The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$)  — the number of choices.
     30 
     31 The second line contains $n$ pairwise distinct integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) — the choices Jose is considering.
     32 
     33 Output
     34 
     35 Print a single integer number — the number of unordered pairs $\{x, y\}$ formed by different numbers from Jose's choices that could make the legend true.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3
     43 2 5 -3
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 2
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 2
     56 3 6
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1
     63 ```
     64 
     65 Note
     66 
     67 Consider the first sample. For the pair $\{2, 5\}$, the situation looks as follows, with the Arrayland markers at $|2| = 2$ and $|5| = 5$, while the Vectorland markers are located at $|2 - 5| = 3$ and $|2 + 5| = 7$:
     68 
     69  ![](https://espresso.codeforces.com/ff962801190d8f92e0e3606aba50277cb8cf0aec.png) 
     70 
     71 The legend is not true in this case, because the interval $[2, 3]$ is not conquered by Vectorland. For the pair $\{5, -3\}$ the situation looks as follows, with Arrayland consisting of the interval $[3, 5]$ and Vectorland consisting of the interval $[2, 8]$:
     72 
     73  ![](https://espresso.codeforces.com/cda8f60357e7d21862f898413d56280555e86041.png) 
     74 
     75 As Vectorland completely contains Arrayland, the legend is true. It can also be shown that the legend is true for the pair $\{2, -3\}$, for a total of two pairs.
     76 
     77 In the second sample, the only pair is $\{3, 6\}$, and the situation looks as follows:
     78 
     79  ![](https://espresso.codeforces.com/1a01b7807f1dd3aecb48bedb360cbaca14d0367c.png) 
     80 
     81 Note that even though Arrayland and Vectorland share $3$ as endpoint, we still consider Arrayland to be completely inside of Vectorland.