[JOIST 2024] 鱼 3 / Fish 3

Luogu

IDLGP10430

Time2000ms

Memory1024MB

DifficultyP6

2024JOISC/JOIST（日本）

JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。 JOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下： - 当第 $ k $ 条鱼（$ 1 \leq k \leq N $）吃掉一块 $ A $ 型食物时，第 $ k $ 条鱼的智力恰好增加 $ D $。 - 当第 $ k $ 条鱼（$ 1 \leq k \leq N $）吃掉一块 $ B $ 型食物时，编号大于等于 $ k $ 的所有鱼的智力都恰好增加 $ 1 $。目前，所有鱼的智力都为 $ 0 $。JOI 君希望使第 $ i $ 条鱼（$ 1 \leq i \leq N $）的智力等于其理想智力 $ C_i $，但这并不总是可能的。因此，他考虑了 $ Q $ 个问题。第 $ j $ 个问题（$ 1 \leq j \leq Q $）如下： - 从所有鱼的智力都为 0 的状态开始，通过重复将食物放入水族箱零次或多次的动作，是否可能达到所有鱼 $ L_j , L_j + 1 ,..., R_j $ 都拥有其精确的理想智力值的状态？此外，如果可能，需要放入水族箱的 A 型食物的最小数量是多少？编写一个程序，给定有关 JOI 君的鱼的信息以及有关问题的信息，回答他的问题。 ## Input 从标准输入读取以下数据： - $ N,D $ - $ C_1,C_2,...,C_N $ - $ Q $ - $ L_1,R_1 $ - $ L_2,R_2 $ - ... - $ L_Q,R_Q $ ## Output 输出共 $Q$ 行。在第 $j$ 行（$ 1 \leq j \leq Q $）中，如果可以达到所有鱼 $ L_j $，$ L_j + 1 $，...，$ R_j $ 拥有其精确的理想智力值的状态，则输出需要放入水族箱的 $A$ 型食物的最小数量。否则，输出 $-1$。 [samples] ## Note #### 样例解释 1 例如，在以下情况下，所有鱼 $1,2,3$ 最终都达到了其精确的理想智力值，且放入水族箱的 $A$ 型食物的数量为 $1$。 - 起初，鱼 $1,2,3,4$ 的智力分别为 $0,0,0,0$。 - 接下来，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $3$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $0,0,1,1$。 - 然后，JOI 君将一块 $A$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $2,0,1,1$。 - 最后，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $3,1,2,2$。 - 由于不放入任何 $A$ 型食物就无法达到所有鱼 $1,2,3$ 的精确理想智力值的状态，输出 $1$。这个样例满足子任务 $1$ 和 $5$ 的约束条件。 ### 约束条件 - $ 1 \leq N \leq 300,000 $。 - $ 1 \leq Q \leq 300,000 $。 - $ 1 \leq D \leq 10^{12} $。 - $ 0 \leq C_i \leq 10^{12} $（$ 1 \leq i \leq N $）。 - $ 1 \leq L_j \leq R_j \leq N $（$ 1 \leq j \leq Q $）。 - 给定值均为整数。 ### 子任务 - （9 分）$ N \leq 3,000 $，$ Q \leq 3,000 $。 - （7 分）$ C_i \leq 1 $（$ 1 \leq i \leq N $）。 - （28 分）$ D = 1 $。 - （20 分）$ C_i \geq C_{i+1} $（$ 1 \leq i \leq N - 1 $）。 - （36 分）无额外约束。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2024] 鱼 3 / Fish 3",
    "description": {
      "content": "JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。 JOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下： - 当第 $ k $ 条鱼（$ 1 \\leq k \\leq N $）吃掉一块 $ A $ 型食",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10430"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JOI 君在一个大水缸中饲养着 $ N $ 条鱼，每条鱼的编号从 $ 1 $ 到 $ N $。\n\nJOI 君有两种类型的鱼食，$ A $ 和 $ B $，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下：\n\n- 当第 $ k $ 条鱼（$ 1 \\leq k \\leq N $）吃掉一块 $ A $ 型食...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments