A7680 | Chalkboard Median
时间限制2s
内存限制1024MB
通过 / 提交0/0
题目描述
黑板上写有一个整数 $X$。
你需要依次处理 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）如下：
> 给定两个整数 $A_i$ 和 $B_i$，将这两个新整数写在黑板上。
>
> 然后，输出此时黑板上所写的 $2i+1$ 个整数的中位数。
你需要依次处理 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）如下：
> 给定两个整数 $A_i$ 和 $B_i$，将这两个新整数写在黑板上。
>
> 然后，输出此时黑板上所写的 $2i+1$ 个整数的中位数。
输入格式
输入从标准输入中按以下格式给出：
> $X$
> $Q$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_Q$ $B_Q$
> $X$
> $Q$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_Q$ $B_Q$
输出格式
输出 $Q$ 行。
第 $i$ 行应包含第 $i$ 个查询的答案。
第 $i$ 行应包含第 $i$ 个查询的答案。
输入输出样例
输入 #1
5 3 2 3 1 2 8 9
输出 #1
3 2 3
输入 #2
1 4 2 3 4 5 6 7 8 9
输出 #2
2 3 4 5
输入 #3
278117031 7 167642909 517897721 148434323 567739597 319926999 481642530 659199879 252516557 49913403 798318034 89701408 892537201 199166668 742285869
输出 #3
278117031 278117031 319926999 319926999 319926999 319926999 319926999
**样例 1 解释：**
在第一次查询中，黑板上写的整数变为 $5, 2, 3$，它们的中位数为 $3$。
在第二次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2$，它们的中位数为 $2$。
在第三次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2, 8, 9$，它们的中位数为 $3$。
### 限制条件
* $1 \le X \le 10^9$
* $1 \le Q \le 2 \times 10^5$
* $1 \le A_i, B_i \le 10^9$
* 所有输入值均为整数。
在第一次查询中，黑板上写的整数变为 $5, 2, 3$，它们的中位数为 $3$。
在第二次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2$，它们的中位数为 $2$。
在第三次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2, 8, 9$，它们的中位数为 $3$。
### 限制条件
* $1 \le X \le 10^9$
* $1 \le Q \le 2 \times 10^5$
* $1 \le A_i, B_i \le 10^9$
* 所有输入值均为整数。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？