「……!」
小向打造出了鑰匙,並用那把鑰匙打開了鐵牢,放出了本被關在牢裡的希爾伯特。
「太好了!這樣應該就沒事了!到底發生什麼事了,希爾伯特?」小向急忙上前關切。
「小向,聽我說……」
希爾伯特還來不及接著說,四周就迴蕩著小向熟悉的聲音……
「一會兒不見了,你進步的真多啊,小向…」
接著,一個身影就突然出現在小向與希爾伯特兩人面前。那是一個外表看起來不是七十就是八十歲的老人,留著一大把長長的白鬍子,身穿素衣。
「師…師父…?真的是師父嗎?」
「是啊,小向。我就是水晶球後,真正的掌鏡人喲。」
「難道這一切都是師父做的嗎?」
「是啊…不論是你與希爾伯特的邂逅,你們在旅館遇到的突發事件,烏龍的洗腦,還有監禁希爾伯特,都是我精心安排的喲。」
「…為…為什麼…師父為什麼要做這種」
「現在是問這種事的時候嗎?」小向的師父不等小向說完,直接打斷她的話,「看看你的四周吧。」
這時小向發現自己身邊突然多了好多紅色果實。
「奇怪…為什麼…魔力不斷地在消散…我…我的魔力…」
「這些紅色果實可不是普通的紅色果實。他們能吸收術者以外的人的魔力。」
「碰!」的一聲,希爾伯特就倒地了。
「希爾伯特!」小向大聲呼喊,但沒有任何回應。
「沒有用的喲。他的魔力已經被吸乾了喲。接著就換你了喲,小向。」
「師父…你…你到底有什麼目的!」
「傻孩子,我栽培你就是為了吸取你的魔力喲。」
「………」
原來,我一直以來相信的人,欺騙了我。
原來,我一直以來的努力,都是徒勞。
原來,我一直以來擁有的夢想,就只是別人的糧食……
如此的負面思想不斷地在小向腦中碰撞。小向的精神幾近崩潰…
「……小…向…」小向突然覺得腳被一個人抓住,而那個人正是希爾伯特,「我…我相信你……不要被他嚇唬了…你只要…做…你應該…做…的…事…就……好…了……」
希爾伯特的手漸漸鬆了開來,整個人又摔回了地上。
說的也是。現在應該做的事情是將紅色果實吸收的魔力全釋放出來,讓希爾伯特恢復。小向想起了之前師父教的東西:只要在地上畫上一個魔法陣,紅色果實便會消失,魔力也會回到持有者身上。不過,紅色果實的吸收能力太強,只要小向在某一個瞬間距離某顆紅色果實的距離小於等於0.5,小向的魔力就會被榨乾,也就只有死路一條了。
為了知道哪些地方會離紅色果實太近,小向冷靜下來觀察了紅色果實的分布。紅色果實的分佈只在座標平面上x座標是$0,1,2,3,\dots,N-1$的點上。而且對於某個$0\leq i\leq N-1$,紅色果實在$x=i$直線上的分布剛好是$(i,D_i),(i,D_i+1),\dots,(i,U_i-1),(i,U_i)$,其中$D_i\leq U_i$是整數。除此之外,小向還發現對於所有$0\leq i<N-1$,$[D_i,U_i]$區間和$[D_{i+1},U_{i+1}]$都有交集。
小向想知道一個好的畫魔法陣的方法,而一個魔法陣是由許多條直線組成的。為此,小向想知道$Q$條給定的直線中,走哪條直線魔力會被榨乾,哪些不會。
本題採用IOIstyle,因此沒有任何輸入。如果你輸入了任何東西,可能會導致各種不可預期的結果。
請記得#include "lib1953.h"
。你必須實作下列兩個函式:
void init(int N, long long D[], long long U[]);
:評測系統將會在執行的一開始呼叫這個函式,傳入紅色果實的分佈,其意義如題敘。每筆測資中這個函式只會被呼叫一次。
int query(long long a, long long b, long long c);
:這個函式會被呼叫$Q$次。這個函式需要回傳是否有一個紅色果實距離直線$ax+by=c$小於等於0.5。如果是的話回傳1,否的話回傳0。保證$a,b$不同時為零。
注意:你不需要實作main函式。
子任務(測資) | 額外限制 | 分數 |
1 (0~4) | $N\leq 100,Q\leq 1000$ $ |D_i|,|U_i|,|a|,|b|,\sqrt{|c|}\leq 100$ | 12 |
2 (5~9) | $N, Q\leq 5000$ $ |D_i|,|U_i|,|a|,|b|,\sqrt{|c|}\leq 10^ 9$ | 12 |
3 (10~14) | $N\leq 10^ 4, Q\leq 5\times 10^ 5$ $ |D_i|,|U_i|,|a|,|b|,\sqrt{|c|}\leq 10$ | 32 |
4 (15~21) | $N, Q\leq 5\times 10^ 5$ $ |D_i|,|U_i|,|a|,|b|,\sqrt{|c|}\leq 10^ 9$ | 44 |
本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA。
這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:N;
第二行:D陣列;
第三行:U陣列;
第四行:Q;
接下來的Q行:a b c;
對於每一次呼叫query
函數,此程式會輸出函數回傳的數值。
Problem Set / Description by Paupière
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 12 |
2 | 5~9 | 12 |
3 | 10~14 | 32 |
4 | 15~21 | 44 |