Maximize Update

AtCoder

IDarc168_d

Time2000ms

Memory256MB

Difficulty—

There are $N$ squares arranged in a row, numbered $1$ to $N$ from left to right. Initially, all squares are white. You can perform the following $M$ types of operations **any number of times in any order**: * Type-$i$ operation: Paint square $L_i$ through square $R_i$ in black. Find the maximum number of times the operations can change the state of the squares. If an operation changes the color of at least one square, that operation is considered to change the state of the squares. ## Constraints * $1 \leq N \leq 500$ * $1 \leq M \leq N(N+1)/2$ * $1 \leq L_i \leq R_i \leq N$ * $(L_i,R_i) \neq (L_j,R_j)$ for all $i \neq j$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_M$ $R_M$ [samples]

Samples

Input #1

Output #1

3

If you perform the operations as follows, they will change the state of the squares three times.

*   Perform type-$2$ operation. Square $1$ is newly painted black.
*   Perform type-$3$ operation. Square $3$ is newly painted black.
*   Perform type-$1$ operation. Square $2$ is newly painted black.

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Maximize Update",
    "description": {
      "content": "There are $N$ squares arranged in a row, numbered $1$ to $N$ from left to right. Initially, all squares are white. You can perform the following $M$ types of operations **any number of times in any or",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc168_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ squares arranged in a row, numbered $1$ to $N$ from left to right. Initially, all squares are white.\nYou can perform the following $M$ types of operations **any number of times in any or...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments