Solutions

AtCoder

IDarc106_c

Time2000ms

Memory256MB

Difficulty—

Two segments $[L_1:R_1]$ and $[L_2:R_2]$ are said to _intersect_ when $L_1 \leq R_2$ and $L_2 \leq R_1$ holds. Consider the following problem $P$: Input: $N$ segments $[L_1: R_1], \cdots, [L_N:R_N]$ $L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N$ are pairwise distinct. Output: the maximum number of segments that can be chosen so that no two of them intersect. Takahashi has implemented a program that works as follows: Sort the given segments in the increasing order of $R_i$ and let the result be $[L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}]$. For each $i = 1, 2, \cdots , N$, do the following: Choose $[L_{p_i}:R_{p_i}]$ if it intersects with none of the segments chosen so far. Print the number of chosen segments. Aoki, on the other hand, has implemented a program that works as follows: Sort the given segments in the increasing order of $L_i$ and let the result be $[L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}]$. For each $i = 1, 2, \cdots , N$, do the following: Choose $[L_{p_i}:R_{p_i}]$ if it intersects with none of the segments chosen so far. Print the number of chosen segments. Given are integers $N$ and $M$. Construct an input for the problem $P$, consisting of $N$ segments, such that the following holds: $$ (\\text{The value printed by Takahashi's program}) - (\\text{The value printed by Aoki's program}) = M $$ ## Constraints * All values in input are integers. * $1 \leq N \leq 2 \times 10^5$ * $-N \leq M \leq N$ ## Input Input is given from Standard Input in the following format: $N$ $M$ [samples]

Samples

Input #1

5 1

Output #1

1 10
8 12
13 20
11 14
2 4

Let us call the five segments Segment $1$, Segment $2$, $\cdots$, Segment $5$.
Takahashi's program will work as follows:

Rearrange the segments into the order Segment $5$, Segment $1$, Segment $2$, Segment $4$, Segment $3$.
Choose Segment $5$.
Skip Segment $1$ (because it intersects with Segment $5$).
Choose Segment $2$.
Skip Segment $4$ (because it intersects with Segment $2$).
Choose Segment $3$.

Thus, Takahashi's program will print $3$.
Aoki's program will work as follows:

Rearrange the segments into the order Segment $1$, Segment $5$, Segment $2$, Segment $4$, Segment $3$.
Choose Segment $1$.
Skip Segment $5$ (because it intersects with Segment $1$).
Skip Segment $2$ (because it intersects with Segment $1$).
Choose Segment $4$.
Skip Segment $3$ (because it intersects with Segment $4$).

Thus, Aoki's program will print $2$.
Here, we have $3 - 2 = 1 \left(= M \right)$, and thus these five segments satisfy the condition.

Input #2

10 -10

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "Solutions",
    "description": {
      "content": "Two segments $[L_1:R_1]$ and $[L_2:R_2]$ are said to _intersect_ when $L_1 \\leq R_2$ and $L_2 \\leq R_1$ holds. Consider the following problem $P$: Input: $N$ segments $[L_1: R_1], \\cdots, [L_N:R_N]$ ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc106_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Two segments $[L_1:R_1]$ and $[L_2:R_2]$ are said to _intersect_ when $L_1 \\leq R_2$ and $L_2 \\leq R_1$ holds.\nConsider the following problem $P$:\n\nInput: $N$ segments $[L_1: R_1], \\cdots, [L_N:R_N]$\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments