「JOC-1A」限时签到

Luogu

IDLGP9515

Time1000ms

Memory128MB

DifficultyP2

贪心O2优化

你现在一条笔直的公路上，我们不妨把这条公路看做成一条数轴，你现在在数轴原点的位置上，此外还有 $n$ 个签到处，第 $i$ 个签到处的坐标为 $x_i$，并且其将在你出发后的第 $a_i$ 个时刻开始营业，每个签到处只有在开始营业了之后你才可以进去签到（签到的时间可以忽略不计），你在每个时刻内至多可移动 $1$ 个单位，你必须在 $t$ 时刻或者在此之前到达坐标为 $f$ 的点（$f\le t$），无论你在规定时间内何时到达 $f$ 点，从 $t$ 时刻起你就必须一直待在 $f$ 点，问你最多能去多少个签到处签到。**请注意，你不需要按照签到处的编号顺序签到。** ## Input 共 $n+1$ 行。第一行，三个整数 $n$、$t$ 和 $f$。接下来 $n$ 行，每行两个整数 $x_i$ 和 $a_i$。 ## Output 共一行，一个非负整数，表示最多能去签到的签到处的数量。 [samples] ## Background 纵使寻不到身外的青春，也总得自己来一掷我身中的迟暮。但暗夜又在那里呢？现在没有星，没有月光以至没有笑的渺茫和爱的翔舞；青年们很平安，而我的面前又竟至于并且没有真的暗夜。绝望之为虚妄，正与希望相同！ ——@duanfeitong 摘自鲁迅《希望》 ## Note ### 样例 $\small\text{1}$ 解释一种可行的行动方案如下：在 $5$ 时刻来到第三个签到处签到，然后在 $7$ 时刻来到第二个签到处签到，最后在 $14$ 时刻来到终点，可以证明最多只能去 $2$ 个签到处签到。 ### 数据规模与约定 **本题采用捆绑测试**。 | $\textbf{Subtask}$ | $\textbf{Number}$ | $\textbf{Special conditions}$| $\textbf{Points}$ | $\textbf{Limit}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1-2$ | $n\leq 10$ | $10$ | $\small\texttt{1s，128MB}$ | | $2$ | $3-4$ | $n\leq 5\times 10^3$ | $15$ | $\small\texttt{1s，128MB}$ | | $3$ | $5$ | $n\leq 10^6$ | $25$ | $\small\texttt{1s，128MB}$ | | $4$ | $6-7$ | $f\leq 10^5$ | $20$ | $\small\texttt{500ms，128MB}$ | | $5$ | $8-9$ | $n\leq 10^6$ | $30$ | $\small\texttt{150ms，10MB}$ | 对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$0\leq f\leq t\leq 10^{18}$，$0\leq x_i\leq f$，$0\leq a_i\leq t$，**不保证签到处的坐标互不相同**。请注意：由于本题当 $n$ 接近 $10^7$ 时数据输入量过大，故我们决定在 $n\leq 10^6$ 的数据上修改时间限制和空间限制以代替 $n\leq 10^7$ 的数据的评测。 **请注意，本题输入数据量较大，建议使用较快的读入方式。** --- 在我永恒的记忆里，你天真地微笑。在我年轻的心中，你是星星之火燃烧。 ——@duanfeitong 摘自祁子《童年》

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「JOC-1A」限时签到",
    "description": {
      "content": "你现在一条笔直的公路上，我们不妨把这条公路看做成一条数轴，你现在在数轴原点的位置上，此外还有 $n$ 个签到处，第 $i$ 个签到处的坐标为 $x_i$，并且其将在你出发后的第 $a_i$ 个时刻开始营业，每个签到处只有在开始营业了之后你才可以进去签到（签到的时间可以忽略不计），你在每个时刻内至多可移动 $1$ 个单位，你必须在 $t$ 时刻或者在此之前到达坐标为 $f$ 的点（$f\\le t$）",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9515"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你现在一条笔直的公路上，我们不妨把这条公路看做成一条数轴，你现在在数轴原点的位置上，此外还有 $n$ 个签到处，第 $i$ 个签到处的坐标为 $x_i$，并且其将在你出发后的第 $a_i$ 个时刻开始营业，每个签到处只有在开始营业了之后你才可以进去签到（签到的时间可以忽略不计），你在每个时刻内至多可移动 $1$ 个单位，你必须在 $t$ 时刻或者在此之前到达坐标为 $f$ 的点（$f\\le t$）...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments