C. Anime

Codeforces

IDCF10263C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Little Lesha studies in the sixth grade. Lesha is not the best performing student, and that's why his interests are rather peculiar. In particular, he finds it exciting to watch Chinese cartoons that are commonly known as anime. Once, Lesha decided to skip school and devote the whole day to his favorite activity — watching anime. However, suddenly, he realized that there is a lot of trash on the shelf where he stores his anime discs. The shelf contains $n$ items. The items are arranged in a row, i.e. can be enumerated from $1$ to $n$. The $i$-th item might be either trash or and anime disc. Lesha remembers that he has exactly $k$ discs, and that the $i$-th disc is located somewhere between the positions $l_i$ and $r_i$, inclusive. Help Lesha clean the shelf and regain hope for a better future. The first line contains two integers separated by space: $n$, $k$. Each of the following $k$ lines also contains two integers: $l_i$, $r_i$. $1 <= n <= 100228$ $0 <= k <= n$ $1 <= l_i <= r_i <= n$ Print $n$ integer numbers, each equal to $0$ or $1$. The $i$-th number should be equal to $1$ if and only if the $i$-th item on the shelf is trash. It is guaranteed that one can always find an unambiguous solution. ## Input The first line contains two integers separated by space: $n$, $k$. Each of the following $k$ lines also contains two integers: $l_i$, $r_i$. $1 <= n <= 100228$$0 <= k <= n$$1 <= l_i <= r_i <= n$ ## Output Print $n$ integer numbers, each equal to $0$ or $1$. The $i$-th number should be equal to $1$ if and only if the $i$-th item on the shelf is trash. It is guaranteed that one can always find an unambiguous solution. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of items on the shelf. Let $ k \in \mathbb{Z}_{\geq 0} $ be the number of anime discs. For each $ i \in \{1, \dots, k\} $, let $ [l_i, r_i] \subseteq \{1, \dots, n\} $ be the interval where the $ i $-th disc is located. **Constraints** 1. $ 1 \leq n \leq 100228 $ 2. $ 0 \leq k \leq n $ 3. For each $ i \in \{1, \dots, k\} $: $ 1 \leq l_i \leq r_i \leq n $ 4. There exists a unique set $ D \subseteq \{1, \dots, n\} $ of size $ k $ such that $ |D \cap [l_i, r_i]| = 1 $ for all $ i \in \{1, \dots, k\} $. **Objective** Output a sequence $ T = (t_1, t_2, \dots, t_n) \in \{0,1\}^n $, where: $$ t_i = \begin{cases} 1 & \text{if } i \notin D \\ 0 & \text{if } i \in D \end{cases} $$ i.e., $ t_i = 1 $ iff the $ i $-th item is trash.

API Response (JSON)

{
  "problem": {
    "name": "C. Anime",
    "description": {
      "content": "Little Lesha studies in the sixth grade. Lesha is not the best performing student, and that's why his interests are rather peculiar. In particular, he finds it exciting to watch Chinese cartoons that ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10263C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little Lesha studies in the sixth grade. Lesha is not the best performing student, and that's why his interests are rather peculiar. In particular, he finds it exciting to watch Chinese cartoons that ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of items on the shelf.  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the number of anime discs.  \nFor each $ i \\in \\{1, \\dots, k\\} $, let $ [l_i, r_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments