{"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, 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.\n\nYou need to perform each operation exactly once, in arbitrary order.\n\nYou 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.\n\n## Input\n\nThe first line contains an integer $n$ ($1\\le n\\le 5\\times 10^3$).\n\nThe $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.\n\n## Output\n\nOutput one integer representing the answer in one line.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9726","tags":["2022","网络流","O2优化","ICPC","bitset","EC Final"],"sample_group":[["5\n2 3\n6 7\n1 9\n5 10\n4 8\n","9\n"]],"created_at":"2026-03-03 11:09:25"}}