2053B.md (2844B)
1 Source: https://codeforces.com/problemset/problem/2053/B 2 3 B. Outstanding Impressionist 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 standard input 16 17 output 18 19 standard output 20 21 If it was so, then let's make it a deal... 22 23 — MayDay, [Gentleness](https://www.youtube.com/watch?v=mtAc_bMYBsM&list=PLj6NQzHFCvkHKIm0Vnk9LH3odqTIBRZ1Q&index=15) 24 25 Even after copying the paintings from famous artists for ten years, unfortunately, Eric is still unable to become a skillful impressionist painter. He wants to forget something, but the white bear phenomenon just keeps hanging over him. 26 27 Eric still remembers $n$ pieces of impressions in the form of an integer array. He records them as $w_1, w_2, \ldots, w_n$. However, he has a poor memory of the impressions. For each $1 \leq i \leq n$, he can only remember that $l_i \leq w_i \leq r_i$. 28 29 Eric believes that impression $i$ is unique if and only if there exists a possible array $w_1, w_2, \ldots, w_n$ such that $w_i \neq w_j$ holds for all $1 \leq j \leq n$ with $j \neq i$. 30 31 Please help Eric determine whether impression $i$ is unique for every $1 \leq i \leq n$, independently for each $i$. Perhaps your judgment can help rewrite the final story. 32 33 Input 34 35 Each test contains multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows. 36 37 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot 10^5$) — the number of impressions. 38 39 Then $n$ lines follow, the $i$-th containing two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq 2\cdot n$) — the minimum possible value and the maximum possible value of $w_i$. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 42 43 Output 44 45 For each test case, output a binary string $s$ of length $n$: for each $1 \leq i \leq n$, if impression $i$ is unique, $s_i=\texttt{1}$; otherwise, $s_i=\texttt{0}$. Do not output spaces. 46 47 Example 48 49 Input 50 51 ``` 52 5 53 54 2 55 56 1 1 57 58 1 1 59 60 4 61 62 1 3 63 64 1 3 65 66 1 3 67 68 1 3 69 70 6 71 72 3 6 73 74 2 2 75 76 1 2 77 78 1 1 79 80 3 4 81 82 2 2 83 84 7 85 86 3 4 87 88 4 4 89 90 4 4 91 92 1 3 93 94 2 5 95 96 1 4 97 98 2 2 99 100 3 101 102 4 5 103 104 4 4 105 106 5 5 107 ``` 108 109 Output 110 111 ``` 112 00 113 1111 114 100110 115 1001111 116 011 117 ``` 118 119 Note 120 121 In the first test case, the only possible array $w$ is $[1, 1]$, making neither impression $1$ nor $2$ unique (since $w_1 = w_2$). 122 123 In the second test case, all impressions can be made unique: 124 125 * For $i = 1$, we can set $w$ to $[1, 3, 2, 3]$, in which $w_1 \neq w_2$, $w_1 \neq w_3$, and $w_1 \neq w_4$; 126 * For $i = 2$, we can set $w$ to $[2, 3, 1, 2]$, in which $w_2 \neq w_1$, $w_2 \neq w_3$, and $w_2 \neq w_4$; 127 * For $i = 3$, we can set $w$ to $[1, 1, 3, 1]$; 128 * For $i = 4$, we can set $w$ to $[2, 3, 3, 1]$. 129 130 In the third test case, for $i = 4$, we can set $w$ to $[3, 2, 2, 1, 3, 2]$. Thus, impression $4$ is unique.