codeforces-scrape

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

242B.md (1557B)


      1 Source: https://codeforces.com/problemset/problem/242/B
      2 
      3 B. Big Segment
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 A coordinate line has *n* segments, the *i*-th segment starts at the position *l**i* and ends at the position *r**i*. We will denote such a segment as [*l**i*, *r**i*].
     22 
     23 You have suggested that one of the defined segments covers all others. In other words, there is such segment in the given set, which contains all other ones. Now you want to test your assumption. Find in the given set the segment which covers all other segments, and print its number. If such a segment doesn't exist, print -1.
     24 
     25 Formally we will assume that segment [*a*, *b*] covers segment [*c*, *d*], if they meet this condition *a* ≤ *c* ≤ *d* ≤ *b*.
     26 
     27 Input
     28 
     29 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the number of segments. Next *n* lines contain the descriptions of the segments. The *i*-th line contains two space-separated integers *l**i*, *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ 109) — the borders of the *i*-th segment.
     30 
     31 It is guaranteed that no two segments coincide.
     32 
     33 Output
     34 
     35 Print a single integer — the number of the segment that covers all other segments in the set. If there's no solution, print -1.
     36 
     37 The segments are numbered starting from 1 in the order in which they appear in the input.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3  
     45 1 1  
     46 2 2  
     47 3 3
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 -1
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 6  
     60 1 5  
     61 2 3  
     62 1 10  
     63 7 10  
     64 7 7  
     65 10 10
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 3
     72 ```