[COTS 2024] 兔子 Zečevi

Luogu

IDLGP10685

Time8000ms

Memory512MB

DifficultyP6

二分2024O2优化COTS（克罗地亚）

数轴上有 $N$ 只兔子，第 $i$ 只兔子位于 $x_i$，起初，第 $i$ 只兔子的能量为 $p_i$。每秒钟会发生如下的事件： - 若存在至少一只兔子的能量为 $0$，则过程结束。 - 否则，每只兔子向右跳跃一个单位长度，同时能量减少 $1$。数轴上分布着 $M$ 根胡萝卜，第 $i$ 根胡萝卜位于位置 $y_i$，质量为 $t_i$ 千克。当某只兔子的位置上有胡萝卜时，它可以选择吃 $a$ 千克的胡萝卜，其中 $a\in [0, y]$，其中 $y$ 为胡萝卜的质量。吃掉 $a$ 千克的胡萝卜后，兔子的能量增加 $a$，胡萝卜的质量减少 $a$。显然兔子一旦停止跳跃，就再也不会跳跃了。在最优的情况下，兔子最多能跳跃多少秒？ ## Input 第一行，两个整数 $N,M$，含义见题面。接下来 $N$ 行，第 $i$ 行两个整数 $x_i,p_i$；接下来 $M$ 行，第 $i$ 行两个整数 $y_i,t_i$。 ## Output 输出一行一个整数，表示最优情况下的答案。 [samples] ## Background 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T3。$\texttt{8s,512M}$。 **请不要滥用本题评测。滥用本题评测将被封号。** ## Note #### 样例解释样例 $1$ 解释：我们用二元组 $(x_i,p_i)$ 表示兔子的位置和能量。跳跃三次后，三只兔子的状态分别为 $(5,1),(10,0),(6,2)$。第二只兔子吃掉 $2$ 千克的胡萝卜，状态变为 $(5,1),(10,2),(6,2)$。接下来一次跳跃之后，三只兔子的状态分别为 $(6,0),(11,1),(7,1)$。第一只兔子吃掉 $3$ 千克胡萝卜，状态变为 $(6,3),(11,1),(7,1)$。接下来一次跳跃之后，三只兔子的状态分别为 $(7,2),(12,0),(8,0)$。由于第二只兔子吃不到胡萝卜，所以跳跃过程终止。可以证明这是最优的答案。 #### 数据范围对于 $100\%$ 的数据，保证： - $1\le N,M\le 10^5$； - $0\le x_i,y_i\le 10^9$； - $0\le p_i,t_i\le 10^9$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $9$ | $N=1$ | | $2$ | $12$ | $M=1$ | | $3$ | $26$ | $N,M\le 1\, 000$ | | $4$ | $34$ | $N,Q\le 50\, 000$ | | $5$ | $19$ | 无额外约束 |

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[COTS 2024] 兔子 Zečevi",
    "description": {
      "content": " 数轴上有 $N$ 只兔子，第 $i$ 只兔子位于 $x_i$，起初，第 $i$ 只兔子的能量为 $p_i$。 每秒钟会发生如下的事件： - 若存在至少一只兔子的能量为 $0$，则过程结束。 - 否则，每只兔子向右跳跃一个单位长度，同时能量减少 $1$。 数轴上分布着 $M$ 根胡萝卜，第 $i$ 根胡萝卜位于位置 $y_i$，质量为 $t_i$ 千克。当某只兔子的位置上有胡萝卜时，它可以选",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10685"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "数轴上有 $N$ 只兔子，第 $i$ 只兔子位于 $x_i$，起初，第 $i$ 只兔子的能量为 $p_i$。\n\n每秒钟会发生如下的事件：\n\n- 若存在至少一只兔子的能量为 $0$，则过程结束。\n- 否则，每只兔子向右跳跃一个单位长度，同时能量减少 $1$。\n\n数轴上分布着 $M$ 根胡萝卜，第 $i$ 根胡萝卜位于位置 $y_i$，质量为 $t_i$ 千克。当某只兔子的位置上有胡萝卜时，它可以选择...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments