[SNCPC2024] 致命公司

Luogu

IDLGP10701

Time1000ms

Memory256MB

DifficultyP5

2024O2优化陕西省赛/邀请赛

Shirost 最近沉迷于一款名为《致命公司》的游戏。在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ 时刻出现在 $x_i$ 号通道距离他 $y_i$ 米远处。对于每个时刻 $j$，以下三个事件将会依次发生： 1. 在该时刻开始时，满足 $t_i = j$ 的弹簧头会出现在 $x_i$ 号通道距离 Shirost $y_i$ 米远处。 2. Shirost 选择凝视任意一个通道。 3. 该通道内的所有弹簧头无法移动，而其他通道中**已经出现**的弹簧头会向他移动 $k$ 米，如果某个弹簧头到达他所在位置，则他将在时刻 $j$ 死亡。 Shirost 想知道他最晚可以活到哪个时刻。换句话说，如果 Shirost 最晚在时刻 $j$ 死亡，那么你需要输出 $j-1$。如果他不会死亡，则输出 $-1$。 ## Input 输入第一行为三个整数 $n,m,k$ ($1 \leq n \leq 5 \times 10^5, 1 \leq m \leq 5 \times 10^5, 1 \leq k \leq 10^{18}$)，由空格隔开，为无限长通道的个数，弹簧头的个数，弹簧头每时刻移动的距离。接下来 $m$ 行，每行三个整数 $t_i,x_i,y_i$ ($1 \leq t_i \leq 10^{18}, 1 \leq x_i \leq n, 1 \leq y_i \leq 10^{18}$)，由空格隔开，描述弹簧头出现的时刻，出现的通道编号，距离 Shirost 有多远。 ## Output 输出仅一行一个整数，表示 Shirost 最晚可以活到哪个时刻。如果他不会死亡，则输出 $-1$。 [samples] ## Note Shirost 可以按如下所述行动： | 时刻 | 凝视的通道 | 弹簧头 $1$ 距离 | 弹簧头 $2$ 距离 | 弹簧头 $3$ 距离 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | 1 | 6 | | | | 2 | 1 | 6 | 5 | | | 3 | 2 | 4 | 5 | 6 | | 4 | 1 | 4 | 3 | 6 | | 5 | 2 | 2 | 3 | 4 | | 6 | 1 | 2 | 1 | 4 | 在第 $7$ 时刻，无论看哪个通道，Shirost 都会在该时刻内被弹簧头杀死。所以答案是 $6$。

Samples

Input #1

Output #1

Input #2

114514 6 1919810
1 1 1
1 1 9
1 4 1
1 5 9
1 1 8
1 4 10

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[SNCPC2024] 致命公司",
    "description": {
      "content": "Shirost 最近沉迷于一款名为《致命公司》的游戏。 在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。 现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10701"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Shirost 最近沉迷于一款名为《致命公司》的游戏。\n\n在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。\n\n现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments