[USACO24JAN] Cannonball B

Luogu

IDLGP10132

Time2000ms

Memory256MB

DifficultyP2

模拟USACO2024

Bessie 已经精通了变成炮弹并沿着长度为 $N$（$1\le N\le 10^5$）的数轴弹跳的艺术，数轴上的位置从左到右编号为 $1,2,\cdots,N$。她从某个整数位置 $S$（$1\le S\le N$）开始，以 $1$ 的起始能量向右弹跳。如果 Bessie 的能量为 $k$，则她将弹跳至距当前位置向前距离 $k$ 处进行下一次弹跳。从 $1$ 到 $N$ 的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在 $0$ 到 $N$ 范围内的整数值。一个数值为 $v$ 的跳板会使 Bessie 的能量增加 $v$ 并反转她的方向。一个数值为 $v$ 的炮击目标会当着陆时能量不小于 $v$ 时被击破。着陆在炮击目标上不会改变 Bessie 的能量和方向。被击破的炮击目标将保持击破状态，Bessie 依然可以该炮击目标上弹跳，同样不会改变能量和方向。如果 Bessie 弹跳无限长的时间或直到她离开数轴，她会击破多少个炮击目标？如果 Bessie 开始时位于一个她可以击破的炮击目标，她会立刻这样做。类似地，如果 Bessie 开始时位于一个跳板，跳板的效果将在她第一次跳跃之前生效。 ## Input 输入的第一行包含 $N$ 和 $S$，其中 $N$ 为数轴的长度，$S$ 为 Bessie 的起始位置。以下 $N$ 行描述了每一个位置。其中第 $i$ 行包含整数 $q_i$ 和 $v_i$，如果位置 $i$ 上有一个跳板则 $q_i=0$，位置 $i$ 上有一个炮击目标则 $q_i=1$，$v_i$ 是位置 $i$ 上的跳板或炮击目标的数值。 ## Output 输出一个整数，为将被击破的炮击目标数量。 [samples] ## Note ### 样例解释 1 Bessie 从坐标 $2$ 开始，这是一个数值为 $1$ 的炮击目标，所以她立刻击破了它。然后她弹跳至坐标 $3$，这是一个数值为 $2$ 的炮击目标，所以她无法击破它。她继续弹跳至坐标 $4$，这改变了她的方向并将她的能量增加了 $1$，达到 $2$。她跳回至坐标 $2$，这是一个已经被击破的炮击目标，所以她继续弹跳。此时，她弹跳至了坐标 $0$，因此她停了下来。她击破了恰好一个炮击目标，位于坐标 $2$。 ### 样例解释 2 Bessie 经过的路径为 $4\to 5\to 3\to 1\to 6$，下一次弹跳将会使她离开数轴（$11$）。她依次击破了炮击目标 $4,3,6$。 ### 测试点性质 - 测试点 $3-5$：$N\le 100$。 - 测试点 $6-10$：$N\le 1000$。 - 测试点 $11-20$：没有额外限制。

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[USACO24JAN] Cannonball B",
    "description": {
      "content": "Bessie 已经精通了变成炮弹并沿着长度为 $N$（$1\\le N\\le 10^5$）的数轴弹跳的艺术，数轴上的位置从左到右编号为 $1,2,\\cdots,N$。她从某个整数位置 $S$（$1\\le S\\le N$）开始，以 $1$ 的起始能量向右弹跳。 如果 Bessie 的能量为 $k$，则她将弹跳至距当前位置向前距离 $k$ 处进行下一次弹跳。 从 $1$ 到 $N$ 的每个整数位置上均",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10132"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie 已经精通了变成炮弹并沿着长度为 $N$（$1\\le N\\le 10^5$）的数轴弹跳的艺术，数轴上的位置从左到右编号为 $1,2,\\cdots,N$。她从某个整数位置 $S$（$1\\le S\\le N$）开始，以 $1$ 的起始能量向右弹跳。 如果 Bessie 的能量为 $k$，则她将弹跳至距当前位置向前距离 $k$ 处进行下一次弹跳。\n\n从 $1$ 到 $N$ 的每个整数位置上均...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments