o340. 披薩快烤焦了!!!(嗎) - 高中生程式解題系統

內容

大黑為了加快烤披薩的進度，買了一個超大的魔法烤箱，能夠裝下 $N$ 個披薩

為了防止披薩烤焦變成黑薩，大黑隨時需要一段區間內連續 $K$ 個披薩烤的時間的最大總和來估計熟度

因為時間緊急，大黑從許多地方搜刮了 $N$ 個二手披薩，因此每個披薩在開始時已經烤過 $A_{i}$ 秒

身為他的得力助手，你需要完成大黑下的 $M$ 個指示，指示有兩種:

1.將 $[l, r]$ 區間內的所有披薩多烤 $d$ 秒。

2.告訴大黑 $[l, r]$ 區間內，連續 $K$ 個披薩烤過的最大時間和，如果區間長度 $< K$ 則輸出0。

請你在每筆第二種指示中輸出答案

若想只拿子題1、3的人請注意以下說明：
由於zerojudge只要看到一筆TLE就不會再繼續跑，所以你如果沒做處理的話，只會拿到子題1的分數。
處理方式可為下：
1.加入assert(n<=1000&&m<=1000)
2.特判(n>1000||m>1000)的case，若發生的話就不要做事

輸入說明

第一行數字 $t$ ，代表總共有 $t$ 筆測資

每筆測資中:
第一行爲 $N$ $M$ $K$
第二行爲陣列 $A$ ，總共有 $N$ 個數字
接下來 $M$ 行有兩種輸入，第一個是1或2的數字，代表選擇哪一種操作：
1 $l$ $r$ $d$ 對應到第一種操作
2 $l$ $r$ 對應到第二種操作

$1 \leq N, M \leq 2 \times 10^{5}$
$1 \leq K \leq m i n (10, N)$
$1 \leq A_{i}, d \leq 10^{6} (1 \leq i \leq N)$
$1 \leq l \leq r \leq N$
保證 $t$ 筆測資中 $N$ 和 $M$ 總和 $\leq 2 \times 10^{5}$

輸出說明

輸出每個操作二的當下區間長度為 $K$ 的最大連續區間和

範例輸入 #1

1
10 7 5
4 2 3 1 7 20 1 2 6 7
2 2 7
1 5 8 3
1 3 5 7
2 1 8
1 5 7 2
1 3 4 9
2 5 9

範例輸出 #1

33
62
61

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (25%): 1.0s , <10M
公開測資點#2 (35%): 1.0s , <1M
公開測資點#3 (30%): 1.5s , <10M

提示：

子題1:
$K = 1, t 筆測資中 N 和 M 總和\leq 1000$
10分

子題2:
$K = 1$
25分

子題3:
$t 筆測資中 N 和 M 總和\leq 1000$
35分

子題4:
原題
30分

標籤:

出處:

[管理者： CGSH (快加油吧~~) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」