TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

21.6% (11/51)

Tags

Description

「……!」
小向打造出了鑰匙,並用那把鑰匙打開了鐵牢,放出了本被關在牢裡的希爾伯特。

「太好了!這樣應該就沒事了!到底發生什麼事了,希爾伯特?」小向急忙上前關切。
「小向,聽我說……」

希爾伯特還來不及接著說,四周就迴蕩著小向熟悉的聲音……

「一會兒不見了,你進步的真多啊,小向…」
接著,一個身影就突然出現在小向與希爾伯特兩人面前。那是一個外表看起來不是七十就是八十歲的老人,留著一大把長長的白鬍子,身穿素衣。
「師…師父…?真的是師父嗎?」
「是啊,小向。我就是水晶球後,真正的掌鏡人喲。」
「難道這一切都是師父做的嗎?」
「是啊…不論是你與希爾伯特的邂逅,你們在旅館遇到的突發事件,烏龍的洗腦,還有監禁希爾伯特,都是我精心安排的喲。」
「…為…為什麼…師父為什麼要做這種」
「現在是問這種事的時候嗎?」小向的師父不等小向說完,直接打斷她的話,「看看你的四周吧。」

這時小向發現自己身邊突然多了好多紅色果實。

「奇怪…為什麼…魔力不斷地在消散…我…我的魔力…」
「這些紅色果實可不是普通的紅色果實。他們能吸收術者以外的人的魔力。」

「碰!」的一聲,希爾伯特就倒地了。
「希爾伯特!」小向大聲呼喊,但沒有任何回應。
「沒有用的喲。他的魔力已經被吸乾了喲。接著就換你了喲,小向。」
「師父…你…你到底有什麼目的!」

「傻孩子,我栽培你就是為了吸取你的魔力喲。」

「………」
原來,我一直以來相信的人,欺騙了我。
原來,我一直以來的努力,都是徒勞。
原來,我一直以來擁有的夢想,就只是別人的糧食……
如此的負面思想不斷地在小向腦中碰撞。小向的精神幾近崩潰…

「……小…向…」小向突然覺得腳被一個人抓住,而那個人正是希爾伯特,「我…我相信你……不要被他嚇唬了…你只要…做…你應該…做…的…事…就……好…了……」
希爾伯特的手漸漸鬆了開來,整個人又摔回了地上。

說的也是。現在應該做的事情是將紅色果實吸收的魔力全釋放出來,讓希爾伯特恢復。小向想起了之前師父教的東西:只要在地上畫上一個魔法陣,紅色果實便會消失,魔力也會回到持有者身上。不過,紅色果實的吸收能力太強,只要小向在某一個瞬間距離某顆紅色果實的距離小於等於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$條給定的直線中,走哪條直線魔力會被榨乾,哪些不會。

Input Format

本題採用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

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Sample Input

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
5
1 3 2 4 7
3 6 4 7 7
2
2 -1 3
0 1 -8

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
1
0

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:N;
第二行:D陣列;
第三行:U陣列;
第四行:Q;
接下來的Q行:a b c;
對於每一次呼叫query函數,此程式會輸出函數回傳的數值。

Problem Source

Problem Set / Description by Paupière

Subtasks

For Testdata: 0 ~ 4, Score: 12
For Testdata: 5 ~ 9, Score: 12
For Testdata: 10 ~ 14, Score: 32
For Testdata: 15 ~ 21, Score: 44
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 1000 65536 262144
16 1000 65536 262144
17 1000 65536 262144
18 1000 65536 262144
19 1000 65536 262144
20 1000 65536 262144
21 1000 65536 262144