[EC Final 2022] Magic

Luogu

IDLGP9726

Time3000ms

Memory16MB

DifficultyP7

2022网络流O2优化ICPCbitsetEC Final

**Warning: Unusual memory limit!** You are given a sequence $a_0,\ldots,a_{2n}$. Initially, all numbers are zero. There are $n$ operations. The $i$-th operation is represented by two integers $l_i, r_i$ ($1\le l_i < r_i\le 2n, 1\le i\le n$), which assigns $i$ to $a_{l_i},\ldots,a_{r_i-1}$. It is guaranteed that all the $2n$ integers, $l_1,l_2,\ldots, l_n, r_1, r_2, \ldots, r_n$, are distinct. You need to perform each operation exactly once, in arbitrary order. You want to maximize the number of $i$ $(0\leq i< 2n)$ such that $a_i\neq a_{i+1}$ after all $n$ operations. Output the maximum number. ## Input The first line contains an integer $n$ ($1\le n\le 5\times 10^3$). The $i$-th line of the next $n$ lines contains a pair of integers $l_i, r_i$ ($1\le l_i < r_i\le 2n$). It is guaranteed that all the $2n$ integers, $l_1,l_2,\ldots, l_n, r_1, r_2, \ldots, r_n$, are distinct. ## Output Output one integer representing the answer in one line. [samples]

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[EC Final 2022] Magic",
    "description": {
      "content": "**Warning: Unusual memory limit!** You are given a sequence $a_0,\\ldots,a_{2n}$. Initially, all numbers are zero.  There are $n$ operations. The $i$-th operation is represented by two integers $l_i,",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 16384
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9726"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**Warning: Unusual memory limit!**\n\nYou are given a sequence $a_0,\\ldots,a_{2n}$. Initially, all numbers are zero. \n\nThere are $n$ operations. The $i$-th operation is represented by two integers $l_i,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments