{"problem":{"name":"[ROI 2018] Innophone","description":{"content":"有一个二元函数 $f(x,y)$，它是这么定义的：  $f(x,y)=\\left\\{ \\begin{array}{rcl} a, & & {\\text{if} \\quad \\quad \\ \\ \\ a \\leq x}\\\\ b, & & {\\text{else if} \\quad b \\leq y}\\\\ 0, & & {\\text{else}} \\end{array} \\right.$ 其中 $a","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9288"},"statements":[{"statement_type":"Markdown","content":"有一个二元函数 $f(x,y)$，它是这么定义的：\n\n $f(x,y)=\\left\\{\n\\begin{array}{rcl}\na, & & {\\text{if} \\quad \\quad \\ \\ \\ a \\leq x}\\\\\nb, & & {\\text{else if} \\quad b \\leq y}\\\\\n0, & & {\\text{else}}\n\\end{array} \\right.$\n\n其中 $a,b$ 为常数。现在给定 $n$ 组 $x,y$，你需要选择合适的 $a,b$，使得 $\\sum_{i=1}^{n} f(x_i,y_i)$ 最大。\n\n## Input\n\n第一行一个整数 $n$，表示 $x$，$y$ 的组数。\n\n后面 $n$ 行，每行两个数 $x_i$，$y_i$。\n\n## Output\n\n一行，一个数，输出 $\\max(\\sum_{i=1}^{n} f(x_i,y_i))$。\n\n[samples]\n\n## Background\n\n译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T3. [Иннофон](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Innophone](http://codeforces.com/gym/102147/problem/B))。 \n\n## Note\n\n对于 $100\\%$ 的数据，$0\\leq y_i\\leq x_i\\leq 10^9$，$1 \\leq n \\leq 1.5 \\times 10^5$。\n\n| 子任务编号 | $n$ | $x,y$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $1 \\leq n \\leq 100$ | $0 \\leq y_i \\leq x_i \\leq 100$ |\n| $2$ | $1 \\leq n \\leq 300$ | $0\\leq y_i\\leq x_i\\leq 10^9$ |\n| $3$ | $1 \\leq n \\leq 3000$ | $0\\leq y_i\\leq x_i\\leq 10^9$ |\n| $4$ | $1 \\leq n \\leq 10^5$ | $y_i = 0$ |\n| $5$ | $1 \\leq n \\leq 10^5$ | $x_i = y_i$ |\n| $6$ | $1 \\leq n \\leq 50000$ | $0\\leq y_i\\leq x_i\\leq 10^9$ | \n| $7$ | $1 \\leq n \\leq 75000$ | $0\\leq y_i\\leq x_i\\leq 10^9$ | \n| $8$ | $1 \\leq n \\leq 10^5$ | $0\\leq y_i\\leq x_i\\leq 10^9$ | \n| $9$ | $1 \\leq n \\leq 1.25 \\times 10^5$ | $0\\leq y_i\\leq x_i\\leq 10^9$ | \n| $10$ | $1 \\leq n \\leq 1.5 \\times 10^5$ | $0\\leq y_i\\leq x_i\\leq 10^9$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9288","tags":["2018","线段树","分块","凸包","扫描线","ROI（俄罗斯）"],"sample_group":[["5\n80 20\n60 50\n40 40\n15 10\n70 30","220"],["1\n50 0","50"]],"created_at":"2026-03-03 11:09:25"}}