codeforces-scrape

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

137C.md (2357B)


      1 Source: https://codeforces.com/problemset/problem/137/C
      2 
      3 C. History
      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 Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.
     22 
     23 Everybody knows that the World history encompasses exactly *n* events: the *i*-th event had continued from the year *a**i* to the year *b**i* inclusive (*a**i* < *b**i*). Polycarpus easily learned the dates when each of *n* events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event *j* includes an event *i* if *a**j* < *a**i* and *b**i* < *b**j*. Your task is simpler: find the number of events that are included in some other event.
     24 
     25 Input
     26 
     27 The first input line contains integer *n* (1 ≤ *n* ≤ 105) which represents the number of events. Next *n* lines contain descriptions of the historical events, one event per line. The *i* + 1 line contains two integers *a**i* and *b**i* (1 ≤ *a**i* < *b**i* ≤ 109) — the beginning and the end of the *i*-th event. No two events start or finish in the same year, that is, *a**i* ≠ *a**j*, *a**i* ≠ *b**j*, *b**i* ≠ *a**j*, *b**i* ≠ *b**j* for all *i*, *j* (where *i* ≠ *j*). Events are given in arbitrary order.
     28 
     29 Output
     30 
     31 Print the only integer — the answer to the problem.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 5  
     39 1 10  
     40 2 9  
     41 3 8  
     42 4 7  
     43 5 6
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 4
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 5  
     56 1 100  
     57 2 50  
     58 51 99  
     59 52 98  
     60 10 60
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 4
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 1  
     73 1 1000000000
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 0
     80 ```
     81 
     82 Note
     83 
     84 In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.
     85 
     86 In the second example all events except the first one are contained in the first.
     87 
     88 In the third example only one event, so the answer is 0.