codeforces-scrape

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

976C.md (1457B)


      1 Source: https://codeforces.com/problemset/problem/976/C
      2 
      3 C. Nested Segments
      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 a sequence *a*1, *a*2, ..., *a**n* of one-dimensional segments numbered 1 through *n*. Your task is to find two distinct indices *i* and *j* such that segment *a**i* lies within segment *a**j*.
     22 
     23 Segment [*l*1, *r*1] lies within segment [*l*2, *r*2] iff *l*1 ≥ *l*2 and *r*1 ≤ *r*2.
     24 
     25 Print indices *i* and *j*. If there are multiple answers, print any of them. If no answer exists, print -1 -1.
     26 
     27 Input
     28 
     29 The first line contains one integer *n* (1 ≤ *n* ≤ 3·105) — the number of segments.
     30 
     31 Each of the next *n* lines contains two integers *l**i* and *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ 109) — the *i*-th segment.
     32 
     33 Output
     34 
     35 Print two distinct indices *i* and *j* such that segment *a**i* lies within segment *a**j*. If there are multiple answers, print any of them. If no answer exists, print -1 -1.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5  
     43 1 10  
     44 2 9  
     45 3 9  
     46 2 3  
     47 2 9
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 2 1
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 3  
     60 1 5  
     61 2 6  
     62 6 20
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 -1 -1
     69 ```
     70 
     71 Note
     72 
     73 In the first example the following pairs are considered correct:
     74 
     75 * (2, 1), (3, 1), (4, 1), (5, 1) — not even touching borders;
     76 * (3, 2), (4, 2), (3, 5), (4, 5) — touch one border;
     77 * (5, 2), (2, 5) — match exactly.