c628: 皮皮的邀約
標籤 :
通過比率 : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-14 19:34

內容

雖說一日之計在於晨,但對皮皮而言,璀璨夜晚才是他的活動時刻。作為夜晚的開始,皮皮每天總會邀請三五好友一同享用晚餐,而今晚他遭遇一個難題 ── 一位朋友臨時有事無法抽身,因此多了個位子。

皮皮的朋友足足有 $\color{black}{200005.6}$ 位那麼多,對他而言,身邊出現空位是最無法忍受的事。他二話不說掏出紙筆,將所有還沒被邀請的朋友列成名單並寫上他們的「人際度」── 這是種皮皮用來衡量一個人是否適合邀請的指標。皮皮接下來會隨意指出若干個區間,並請你找出區間中「人際度」最高的一位朋友好讓他提出邀約(你只要回答該位朋友的人際度)。儘管這個問題看起來就像第三組測資一樣簡單,皮皮卻立即提出奇怪的限制:只要區間中存在多位擁有同樣人際度的朋友,就必須將他們以兩兩一組的方式從該次選擇剔除。

在漫長的等待中,皮皮逐漸失去耐心,你得在每次詢問後馬上告訴他答案,而非在最後一次回答。

輸入說明

第一行有三個正整數 $\color{black}{N, \space Q, \space O \space (1 \le N, Q \le 200000, \space O \in \{0, 1\})}$ ,分別代表朋友數量、詢問次數以及皮皮是否已失去耐心。

第二行為一整數序列,表示朋友的人際度 $\color{black}{S_1 \sim S_N}$ ($\color{black}{1 \le S_i \le 10^9}$)。

接下來 $\color{black}{Q}$ 行分別有兩個正整數 $\color{black}{l, r}$ 表示詢問區間。
若 $\color{black}{O = 0}$,你不用對 $\color{black}{l, r}$ 做任何操作;
若 $\color{black}{O = 1}$,為模擬實際情形,$\color{black}{l, r}$ 應替換為 $\color{black}{(l + ans) \space \% \space N + 1}$, $\color{black}{(r + ans) \space \% \space N + 1}$,其中 $\color{black}{ans}$ 代表前一次詢問的答案(第一次前視為 $\color{black}{0}$)。

保證替換前後 $\color{black}{1 \le l, \space r \le N}$。

輸出說明

輸出皮皮邀約對象的人際度。

如果沒有能選擇的朋友,請輸出 $\color{black}{0}$。

範例輸入
範例輸入一:
5 3 0
1 2 2 1 2
1 3
2 5
1 4

範例輸入二:
5 3 1
1 2 2 1 2
5 2
5 3
3 1

範例輸出
範例輸出一:
1
2
0

範例輸出二:
1
2
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1M
公開 測資點#1 (5%): 2.0s , <1M
公開 測資點#2 (10%): 2.0s , <10M
公開 測資點#3 (10%): 2.0s , <10M
公開 測資點#4 (10%): 2.0s , <10M
公開 測資點#5 (6%): 2.0s , <10M
公開 測資點#6 (6%): 2.0s , <10M
公開 測資點#7 (8%): 2.0s , <10M
公開 測資點#8 (8%): 2.0s , <10M
公開 測資點#9 (8%): 2.0s , <10M
公開 測資點#10 (8%): 2.0s , <10M
公開 測資點#11 (8%): 2.0s , <10M
公開 測資點#12 (8%): 2.0s , <10M
提示 :

範例輸入二和範例輸入一的詢問區間一模一樣。

測資點 $\color{black}{0 \sim 1 (10\%)}$ ,$\color{black}{1 \le N, Q \le 1000, \space O = 0}$。

測資點 $\color{black}{2 \sim 4 (30\%)}$ ,$\color{black}{O = 0}$。

測資點 $\color{black}{5 \sim 6 (12\%)}$ ,$\color{black}{O = 1}$ ,任兩位朋友的人際度必定相異。

測資點 $\color{black}{7 \sim 12 (48\%)}$ ,$\color{black}{O = 1}$。

標籤:
出處:
[管理者:
icube (輸光光)
]


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