codeforces-scrape

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

2164C.md (2163B)


      1 Source: https://codeforces.com/problemset/problem/2164/C
      2 
      3 C. Dungeon
      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 now in a dungeon with $n$ swords, facing $m$ monsters.
     22 
     23 The damage of the $i$-th sword is $a_i$, and the life value of the $i$-th monster is $b_i$. A sword with damage $x$ can kill a monster with life value $y$ if and only if $x \ge y$.
     24 
     25 After killing the $i$-th monster with a sword of damage $x$, this sword disappears. Then, if $c_i \gt 0$, you will obtain a new sword with damage $\max(x, c_i)$; otherwise, you gain nothing.
     26 
     27 Now you want to know the maximum number of monsters you can kill. Note that you can kill each monster at most once.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^4$). The description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 2 \cdot 10^5$).
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9)$.
     36 
     37 The third line of each test case contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \le b_i \le 10^9)$.
     38 
     39 The fourth line of each test case contains $m$ integers $c_1, c_2, \ldots, c_m$ ($0 \le c_i \le 10^9)$.
     40 
     41 It is guaranteed that the sum of $n$ and $m$ over all test cases does not exceed $2 \cdot 10^5$, respectively.
     42 
     43 Output
     44 
     45 For each test case output one integer — the maximum number of monsters you can kill.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 3 2
     55 
     56 2 2 2
     57 
     58 2 3
     59 
     60 3 2
     61 
     62 2 3
     63 
     64 2 3
     65 
     66 2 3 4
     67 
     68 0 0 0
     69 
     70 3 5
     71 
     72 1 7 7
     73 
     74 6 6 2 2 2
     75 
     76 2 0 0 7 2
     77 
     78 4 4
     79 
     80 1 5 3 5
     81 
     82 7 4 6 5
     83 
     84 0 0 1 6
     85 
     86 2 2
     87 
     88 1 1000000000
     89 
     90 1000000000 1
     91 
     92 1000000000 0
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 2
     99 
    100 2
    101 
    102 5
    103 
    104 3
    105 
    106 2
    107 ```
    108 
    109 Note
    110 
    111 [Visualizer link](https://codeforces.com/assets/contests/2164/C_oochei8Kaijaiz8hah8l.html)
    112 
    113 In the first test case, you can first kill monster #1 using sword #1, and obtain a new sword with damage $\max(2,3)=3$. You can then use this sword to kill monster #2.
    114 
    115 In the second test case, you can't obtain any new swords because all $c_i=0$, so you can only kill monster #1 and #2 with your two existing swords.