今天ジュンコ又要做胃袋訓練了 hehe。
有 $Q\ (\leq 3 \times 10^6)$ 個食物，這些食物的美味度介於 $0 \sim 255$ 之間，在第 $i$ 個時間她會吃下一個美味度為 $v_i$ 的食物，接著在吃完後需要回答在一段時間 $(l_i,r_i)$ 吃的食物中美味度最大值是多少，為了不能作弊 (如假吃之類的) ，詢問的時間中一定會至少佔有目前吃的食物的量的一半 (一半沒整除的話自動向上取整)，也就是給你 $l_i,r_i$ 滿足 $1 \le l_i \le r_i \le i$ 和 $(r_i - l_i +1) \geq \lceil i/2 \rceil$，問 $max(v_{l_i}, v_{l_i+1}, ... v_{r_i})$ 的值?
因為胃的容量有限，只有 5MB，吃太多會吐出來，所以請你想想怎麼解決這個問題。
輸入的第一行有個正整數代表 $Q$。
接著有 $Q$ 行，第 $i$ 行有三個整數以空格隔開，分別代表 $v_i, l_i, r_i$。
輸出 $Q$ 行對應的 $max(v_{l_i}, v_{l_i+1}, ... v_{r_i})$ 的值。
6 3 1 1 0 2 2 5 1 2 4 1 4 6 2 5 4 1 4
3 0 3 5 6 5
公開 測資點#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) , max(3) = 3$
$S = (3,0) , max(0) = 0$
$S = (3,0,5) , max(3,0) = 3$
$S = (3,0,5,4) , max(3,0,5,4) = 5$
$S = (3,0,5,4,6) , max(0,5,4,6) = 6$
$S = (3,0,5,4,6,4) , max(3,0,5,4) = 5$
配分
$(25\%)\ Q \le 10^3$
$(25\%)\ Q \le 10^5$
$(50\%)$ 無其他限制
Authored by r1cky
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||