a522: Mining for Gold (hard version)
標籤 : segment
通過比率 : 9人/12人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-12 00:35

內容

a521: Mining for gold (easy version) 進階題

Amelia Watson 想要蓋一條 Holo Railway

為此他需要很多的鐵軌,包括一般鐵軌和動力鐵軌

因為在 Minecraft 中,鐵不是什麼稀有的資源

所以只要有足夠多的黃金,鐵軌就能繼續蓋

於是 Amelia 開始挖黃金,但他不擅長算數

他不知道挖到的黃金該搭配多少鐵軌

 

給定以下兩種操作

1. 在礦洞的第 $x$ 格挖到黃金

2. 求出礦洞內 $[l,r]$ (左閉右閉區間)範圍中挖到的黃金做成動力鐵軌後需要搭配多少一般鐵軌

 

已知動力鐵軌的合成配方如下

( $6$ 個黃金能換 $6$ 個動力鐵軌)

而根據 investigation ,一個動力鐵軌可以接 $8$ 個一般鐵軌

輸入說明

多測資點,每個測資點單筆測資

第一行有一正整數 $n$ 代表有多少筆操作

接下來有 $n$ 行,每行代表一個操作

輸入 1 x 代表在礦洞的第 $x$ 格挖到黃金

輸入 2 l r 代表詢問(問什麼自己看題敘)

對於所有測資, $n\leq 5\times 10^5$ , $1\leq x,l,r\leq 10^8$

輸出說明

對於每筆詢問,輸出區間內挖到的黃金做成動力鐵軌後需要搭配多少一般鐵軌

範例輸入
12
1 1
1 2
1 5
1 5
2 1 10
1 4
1 3
1 6
1 9
1 8
1 7
2 1 10
範例輸出
0
48
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
提示 :
標籤:
segment
出處:
[管理者:
fdhs107_KonChin... (konchin)
]


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