codeforces-scrape

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

417B.md (1989B)


      1 Source: https://codeforces.com/problemset/problem/417/B
      2 
      3 B. Crash
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 During the "Russian Code Cup" programming competition, the testing system stores all sent solutions for each participant. We know that many participants use random numbers in their programs and are often sent several solutions with the same source code to check.
     22 
     23 Each participant is identified by some unique positive integer *k*, and each sent solution *A* is characterized by two numbers: *x* — the number of different solutions that are sent before the first solution identical to *A*, and *k* — the number of the participant, who is the author of the solution. Consequently, all identical solutions have the same *x*.
     24 
     25 It is known that the data in the testing system are stored in the chronological order, that is, if the testing system has a solution with number *x* (*x* > 0) of the participant with number *k*, then the testing system has a solution with number *x* - 1 of the same participant stored somewhere before.
     26 
     27 During the competition the checking system crashed, but then the data of the submissions of all participants have been restored. Now the jury wants to verify that the recovered data is in chronological order. Help the jury to do so.
     28 
     29 Input
     30 
     31 The first line of the input contains an integer *n* (1 ≤ *n* ≤ 105) — the number of solutions. Each of the following *n* lines contains two integers separated by space *x* and *k* (0 ≤ *x* ≤ 105; 1 ≤ *k* ≤ 105) — the number of previous unique solutions and the identifier of the participant.
     32 
     33 Output
     34 
     35 A single line of the output should contain «YES» if the data is in chronological order, and «NO» otherwise.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 2  
     43 0 1  
     44 1 1
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 YES
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 4  
     57 0 1  
     58 1 2  
     59 1 1  
     60 0 2
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 NO
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 4  
     73 0 1  
     74 1 1  
     75 0 1  
     76 0 2
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 YES
     83 ```