{"problem":{"name":"[POI 2023/2024 R1] Zapobiegliwy student","description":{"content":"考虑如下的一个简单问题： > 你有 $n$ 个线段在数轴上，你要选出尽量多的线段，使它们两两不交。 我知道你一定会做，但你需要解决这个： 你有 $n$ 个线段在数轴上，你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$，即最大化 $k$。 满足 $k+1$ 个要求： - $u_1,u_2,\\cdots,u_k$ 两两不交。 - $v_1,u_2,u_3,\\cdots,u_k$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9925"},"statements":[{"statement_type":"Markdown","content":"考虑如下的一个简单问题：\n\n> 你有 $n$ 个线段在数轴上，你要选出尽量多的线段，使它们两两不交。\n\n我知道你一定会做，但你需要解决这个：\n\n你有 $n$ 个线段在数轴上，你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$，即最大化 $k$。\n\n满足 $k+1$ 个要求：\n\n- $u_1,u_2,\\cdots,u_k$ 两两不交。\n- $v_1,u_2,u_3,\\cdots,u_k$ 两两不交。\n- $u_1,v_2,u_3,u_4,\\cdots,u_k$ 两两不交。\n- $\\cdots$\n- $u_1,u_2,\\cdots,u_{k-1},v_k$ 两两不交。\n\n其中 $\\forall i$，$u_i$ 与 $v_i$ 不能相同。\n\n## Input\n\n第一行一个正整数 $n(n\\geq2)$。\n\n接下来 $n$ 行每行两个正整数 $a_i,b_i(1\\leq a_i<b_i\\leq10^9)$，表示一个线段的两个端点。\n\n两个线段 $i,j$ 不交当且仅当 $b_i\\leq a_j$ 或 $b_j\\leq a_i$。\n\n## Output\n\n第一行一个正整数 $k$。\n\n接下来 $k$ 行，每行两个正整数 $u_i,v_i$，表示一对线段的编号。\n\n[samples]\n\n## Background\n\n译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Zapobiegliwy student](https://sio2.mimuw.edu.pl/c/oi31-1/p/zap/)。\n\n## Note\n\n如果你的第一行正确但是方案不对（可以不输出方案，此时不要有换行），你能得到 $50\\%$ 的分数。\n\n如果你的方案合法并且第一行和答案相差不超过 $1$，你能得到 $15\\%$ 的分数。\n\n| 子任务编号 | 限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 | $n\\leq3000$ | 40 |\n| 2 | $n\\leq500000$ | 60 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9925","tags":["贪心","POI（波兰）","2023","Special Judge","构造"],"sample_group":[["8\n1 5\n3 10\n4 8\n9 12\n11 16\n14 15\n20 22\n15 21\n","3\n1 3\n4 6\n8 7\n"],["见附件","见附件"],["见附件","见附件"]],"created_at":"2026-03-03 11:09:25"}}