codeforces-scrape

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

639A.md (3619B)


      1 Source: https://codeforces.com/problemset/problem/639/A
      2 
      3 A. Bear and Displayed Friends
      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 Limak is a little polar bear. He loves connecting with other bears via social networks. He has *n* friends and his relation with the *i*-th of them is described by a unique integer *t**i*. The bigger this value is, the better the friendship is. No two friends have the same value *t**i*.
     22 
     23 Spring is starting and the Winter sleep is over for bears. Limak has just woken up and logged in. All his friends still sleep and thus none of them is online. Some (maybe all) of them will appear online in the next hours, one at a time.
     24 
     25 The system displays friends who are online. On the screen there is space to display at most *k* friends. If there are more than *k* friends online then the system displays only *k* best of them — those with biggest *t**i*.
     26 
     27 Your task is to handle queries of two types:
     28 
     29 * "1 id" — Friend *id* becomes online. It's guaranteed that he wasn't online before.
     30 * "2 id" — Check whether friend *id* is displayed by the system. Print "YES" or "NO" in a separate line.
     31 
     32 Are you able to help Limak and answer all queries of the second type?
     33 
     34 Input
     35 
     36 The first line contains three integers *n*, *k* and *q* (1 ≤ *n*, *q* ≤ 150 000, 1 ≤ *k* ≤ *min*(6, *n*)) — the number of friends, the maximum number of displayed online friends and the number of queries, respectively.
     37 
     38 The second line contains *n* integers *t*1, *t*2, ..., *t**n* (1 ≤ *t**i* ≤ 109) where *t**i* describes how good is Limak's relation with the *i*-th friend.
     39 
     40 The *i*-th of the following *q* lines contains two integers *type**i* and *id**i* (1 ≤ *type**i* ≤ 2, 1 ≤ *id**i* ≤ *n*) — the *i*-th query. If *type**i* = 1 then a friend *id**i* becomes online. If *type**i* = 2 then you should check whether a friend *id**i* is displayed.
     41 
     42 It's guaranteed that no two queries of the first type will have the same *id**i* becuase one friend can't become online twice. Also, it's guaranteed that at least one query will be of the second type (*type**i* = 2) so the output won't be empty.
     43 
     44 Output
     45 
     46 For each query of the second type print one line with the answer — "YES" (without quotes) if the given friend is displayed and "NO" (without quotes) otherwise.
     47 
     48 Examples
     49 
     50 Input
     51 
     52 ```
     53 4 2 8  
     54 300 950 500 200  
     55 1 3  
     56 2 4  
     57 2 3  
     58 1 1  
     59 1 2  
     60 2 1  
     61 2 2  
     62 2 3
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 NO  
     69 YES  
     70 NO  
     71 YES  
     72 YES
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 6 3 9  
     79 50 20 51 17 99 24  
     80 1 3  
     81 1 4  
     82 1 5  
     83 1 2  
     84 2 4  
     85 2 2  
     86 1 1  
     87 2 4  
     88 2 3
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 NO  
     95 YES  
     96 NO  
     97 YES
     98 ```
     99 
    100 Note
    101 
    102 In the first sample, Limak has 4 friends who all sleep initially. At first, the system displays nobody because nobody is online. There are the following 8 queries:
    103 
    104 1. "1 3" — Friend 3 becomes online.
    105 2. "2 4" — We should check if friend 4 is displayed. He isn't even online and thus we print "NO".
    106 3. "2 3" — We should check if friend 3 is displayed. Right now he is the only friend online and the system displays him. We should print "YES".
    107 4. "1 1" — Friend 1 becomes online. The system now displays both friend 1 and friend 3.
    108 5. "1 2" — Friend 2 becomes online. There are 3 friends online now but we were given *k* = 2 so only two friends can be displayed. Limak has worse relation with friend 1 than with other two online friends (*t*1 < *t*2, *t*3) so friend 1 won't be displayed
    109 6. "2 1" — Print "NO".
    110 7. "2 2" — Print "YES".
    111 8. "2 3" — Print "YES".