[蓝桥杯 2018 省 A] 三体攻击

Luogu

IDLGP8666

Time2000ms

Memory256MB

DifficultyP4

2018二分差分蓝桥杯省赛

三体人将对地球发起攻击。为了抵御攻击，地球人派出了 $A\times B\times C$ 艘战舰，在太空中排成一个 $A$ 层 $B$ 行 $C$ 列的立方体。其中，第 $i$ 层第 $j$ 行第 $k$ 列的战舰（记为战舰 $(i, j, k)$）的生命值为 $d(i, j, k)$。三体人将会对地球发起 $m$ 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 $t$ 轮攻击用 $7$ 个参数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$ 描述；所有满足 $i\in [la_t, ra_t],j\in [lb_t, rb_t],k\in [lc_t, rc_t]$ 的战舰 $(i, j, k)$ 会受到 $h_t$ 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。 ## Input 从标准输入读入数据。第一行包括 $4$ 个正整数 $A$，$B$，$C$，$m$；第二行包含 $A\times B\times C$ 个整数，其中第 $((i − 1)\times B + (j − 1)) \times C + (k − 1)+1$ 个数为 $d(i, j, k)$；第 $3$ 到第 $m + 2$ 行中，第 $(t + 2)$ 行包含 $7$ 个正整数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$。 ## Output 输出到标准输出。输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。 [samples] ## Note **【样例解释】** 在第 $2$ 轮攻击后，战舰 $(1,1,1)$ 总共受到了 $2$ 点伤害，超出其防御力导致爆炸。 **【数据约定】** 对于 $10\%$ 的数据，$B = C = 1$；对于 $20\%$ 的数据，$C = 1$；对于 $40\%$ 的数据，$A\times B \times C, m\le10000$；对于 $70\%$ 的数据，$A, B, C \le 200$；对于所有数据，$1\le A\times B\times C \le 10^6$，$1\le m \le 10^6$，$0 \le (i, j, k)$, $h_t\le 10^9$。

Samples

Input #1

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2018 省 A] 三体攻击",
    "description": {
      "content": "三体人将对地球发起攻击。为了抵御攻击，地球人派出了 $A\\times B\\times C$ 艘战舰，在太空中排成一个 $A$ 层 $B$ 行 $C$ 列的立方体。其中，第 $i$ 层第 $j$ 行第 $k$ 列的战舰（记为战舰 $(i, j, k)$）的生命值为 $d(i, j, k)$。 三体人将会对地球发起 $m$ 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8666"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "三体人将对地球发起攻击。为了抵御攻击，地球人派出了 $A\\times B\\times C$ 艘战舰，在太空中排成一个 $A$ 层 $B$ 行 $C$ 列的立方体。其中，第 $i$ 层第 $j$ 行第 $k$ 列的战舰（记为战舰 $(i, j, k)$）的生命值为 $d(i, j, k)$。\n\n三体人将会对地球发起 $m$ 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments