2249A.md (2714B)
1 Source: https://codeforces.com/problemset/problem/2249/A 2 3 A. Rank Subsequence 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 $n$ elements arranged in a line, numbered $1, 2, \ldots, n$ from left to right. 22 23 You may delete any number of elements (possibly none). The remaining elements form a subsequence and keep their relative order. Let the length of this subsequence be $m$. If the element with original index $i$ becomes the $j$-th element of the subsequence ($1 \le j \le m$), define 24 25 * its left rank as $j$, and 26 * its right rank as $m - j + 1$. 27 28 For each element, you are given two integer segments $[l_i, r_i]$ and $[u_i, v_i]$. The $i$-th element is valid in a subsequence of length $m$ if and only if, when it occupies position $j$ in that subsequence, both of the following hold: 29 30 * Its left rank is not in the range $[l_i, r_i]$ (i.e., $j \notin [l_i, r_i]$); 31 * Its right rank is not in the range $[u_i, v_i]$ (i.e., $m - j + 1 \notin [u_i, v_i]$). 32 33 A subsequence is valid if every element remaining in it is valid. 34 35 Find the maximum possible length of a valid subsequence. The answer may be $0$. 36 37 Input 38 39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows. 40 41 The first line of each test case contains a single integer $n$ ($1\le n\le 5000$) — the number of elements. 42 43 Then $n$ lines follow, the $i$-th line containing the four integers $l_i$, $r_i$, $u_i$, and $v_i$ ($1\le i\le n$, $1\le l_i\le r_i\le n$, $1\le u_i\le v_i\le n$). 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$. 46 47 Output 48 49 For each test case, print one integer — the maximum possible length of a valid subsequence. 50 51 Example 52 53 Input 54 55 ``` 56 5 57 58 1 59 60 1 1 1 1 61 62 4 63 64 2 2 2 2 65 66 1 1 1 1 67 68 1 1 1 1 69 70 1 1 2 2 71 72 5 73 74 1 1 3 3 75 76 2 2 2 2 77 78 3 3 1 1 79 80 1 5 1 5 81 82 5 5 5 5 83 84 2 85 86 2 2 1 1 87 88 1 1 2 2 89 90 6 91 92 1 1 6 6 93 94 1 2 5 6 95 96 2 3 4 5 97 98 3 4 3 4 99 100 4 5 2 3 101 102 5 6 1 2 103 ``` 104 105 Output 106 107 ``` 108 0 109 110 4 111 112 3 113 114 2 115 116 3 117 ``` 118 119 Note 120 121 In the first test case, the only element cannot form a valid subsequence of length $1$, so the answer is $0$. 122 123 In the second test case, all $4$ elements can be kept. Their pairs of left and right ranks are $(1, 4)$, $(2, 3)$, $(3, 2)$, and $(4, 1)$, respectively, and all of them are valid. 124 125 In the third test case, one optimal choice is to keep the elements with original indices $2$, $3$, and $5$. 126 127 In the fourth test case, keeping both elements yields a valid subsequence of length $2$. Note that no valid subsequence of length $1$ exists. 128 129 In the fifth test case, one optimal choice is to keep the elements with original indices $3$, $4$, and $5$.