q068. 超級胃袋測試 - 高中生程式解題系統

內容

今天ジュンコ又要做胃袋訓練了 hehe。

有 $Q (\leq 3 \times 10^{6})$ 個食物，這些食物的美味度介於 $0 \sim 255$ 之間，在第 $i$ 個時間她會吃下一個美味度為 $v_{i}$ 的食物，接著在吃完後需要回答在一段時間 $(l_{i}, r_{i})$ 吃的食物中美味度最大值是多少，為了不能作弊 (如假吃之類的) ，詢問的時間中一定會至少佔有目前吃的食物的量的一半 (一半沒整除的話自動向上取整)，也就是給你 $l_{i}, r_{i}$ 滿足 $1 \leq l_{i} \leq r_{i} \leq i$ 和 $(r_{i} - l_{i} + 1) \geq ⌈ i / 2 ⌉$ ，問 $m a x (v_{l_{i}}, v_{l_{i} + 1}, . . . v_{r_{i}})$ 的值?

因為胃的容量有限，只有 5MB，吃太多會吐出來，所以請你想想怎麼解決這個問題。

輸入說明

輸入的第一行有個正整數代表 $Q$ 。

接著有 $Q$ 行，第 $i$ 行有三個整數以空格隔開，分別代表 $v_{i}, l_{i}, r_{i}$ 。

輸出說明

輸出 $Q$ 行對應的 $m a x (v_{l_{i}}, v_{l_{i} + 1}, . . . v_{r_{i}})$ 的值。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 5 MB
公開測資點#0 (25%): 3.0s , <1M
公開測資點#1 (25%): 3.0s , <10M
公開測資點#2 (25%): 3.0s , <50M
公開測資點#3 (25%): 3.0s , >50M

提示：

這時有個叫 becaidorz 的先生跑出來說 : #include <bitsc++> 或 #include <iostream> 後很可能就會超過限制了，建議 #include <cstdio> 或其他不會超過限制的函式庫。

範例 #1

以下為依序吃下的食物序列 $S$ 和查詢。

$S = (3), m a x (3) = 3$

$S = (3, 0), m a x (0) = 0$

$S = (3, 0, 5), m a x (3, 0) = 3$

$S = (3, 0, 5, 4), m a x (3, 0, 5, 4) = 5$

$S = (3, 0, 5, 4, 6), m a x (0, 5, 4, 6) = 6$

$S = (3, 0, 5, 4, 6, 4), m a x (3, 0, 5, 4) = 5$

配分

$(25 %) Q \leq 10^{3}$

$(25 %) Q \leq 10^{5}$

$(50 %)$ 無其他限制

Authored by r1cky

標籤:

優化資料結構

出處:

ジュンコの胃袋のびのびパズル [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

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