P11916 [PA 2025] 学区房 / Szkoła

PA 2025 R2C.

有 $n$ 栋建筑在一条笔直的马路上，自西向东依次编号为 $1\sim n$。相邻两栋建筑的距离为 $1$ 米。 有 $m$ 个两两不交的区间 $[l_i,r_i]$，表示编号在 $[l_i,r_i]$ 内的房子**不**提供租赁服务。 有一所学校，在编号为 $s$ 的建筑中。保证编号为 $s$ 的建筑**不**提供租赁服务。 现在想要选择一栋提供租赁服务的建筑 $p$，最小化到学校的距离（即最小化 $|s-p|$）。请帮忙求出这栋建筑的编号。

第一行，三个正整数 $n,m,s$。 接下来 $m$ 行，每行两个正整数 $l_i,r_i$。 数据保证： - 编号为 $s$ 的建筑**不**提供租赁服务； - $m$ 个区间两两不交； - 至少存在一栋建筑提供租赁服务。

输出一个正整数，表示选择建筑的编号。 特别地，若有多解，输出最小的那个编号。

### 样例解释 - 样例 $1$ 解释：$p=4,10$ 是两个解。由于要求编号最小，输出 $4$。 - 样例 $2$ 解释：只有唯一的一栋提供租赁服务的建筑，即编号 $14$ 的建筑。 ### 数据范围 - $ 2 \leq n \leq 10^{12}$； - $1 \leq m \leq 1000$； - $1 \leq s \leq n $； - 编号为 $s$ 的建筑**不**提供租赁服务； - $m$ 个区间两两不交； - 至少存在一栋建筑提供租赁服务。