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.