codeforces-scrape

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

1915F.md (1823B)


      1 Source: https://codeforces.com/problemset/problem/1915/F
      2 
      3 F. Greetings
      4 
      5 time limit per test
      6 
      7 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 There are $n$ people on the number line; the $i$-th person is at point $a_i$ and wants to go to point $b_i$. For each person, $a_i \lt b_i$, and the starting and ending points of all people are distinct. (That is, all of the $2n$ numbers $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ are distinct.)
     22 
     23 All the people will start moving simultaneously at a speed of $1$ unit per second until they reach their final point $b_i$. When two people meet at the same point, they will greet each other once. How many greetings will there be?
     24 
     25 Note that a person can still greet other people even if they have reached their final point.
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of people.
     32 
     33 Then $n$ lines follow, the $i$-th of which contains two integers $a_i$ and $b_i$ ($-10^9 \leq a_i \lt b_i \leq 10^9$) — the starting and ending positions of each person.
     34 
     35 For each test case, all of the $2n$ numbers $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ are distinct.
     36 
     37 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer denoting the number of greetings that will happen.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 2
     51 
     52 2 3
     53 
     54 1 4
     55 
     56 6
     57 
     58 2 6
     59 
     60 3 9
     61 
     62 4 5
     63 
     64 1 8
     65 
     66 7 10
     67 
     68 -2 100
     69 
     70 4
     71 
     72 -10 10
     73 
     74 -5 5
     75 
     76 -12 12
     77 
     78 -13 13
     79 
     80 5
     81 
     82 -4 9
     83 
     84 -2 5
     85 
     86 3 4
     87 
     88 6 7
     89 
     90 8 10
     91 
     92 4
     93 
     94 1 2
     95 
     96 3 4
     97 
     98 5 6
     99 
    100 7 8
    101 ```
    102 
    103 Output
    104 
    105 ```
    106 1
    107 9
    108 6
    109 4
    110 0
    111 ```
    112 
    113 Note
    114 
    115 In the first test case, the two people will meet at point $3$ and greet each other.