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

No. Testdata Range Score
1 0~4 12
2 5~9 12
3 10~14 32
4 15~21 44

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4
20 1000 65536 262144 4
21 1000 65536 262144 4