TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

35.7% (5/14)

Submission's AC Ratio

4.5% (22/486)

Tags

Description

有一天,大陸人閒來無事時翻著其他國家的人寫的論文。忽然,有一個演算法吸引了他的注意:這個演算法可以在$O(C)$預處理之後,$O(1)$查詢兩個小於等於C的數的最大公因數。
瞬間,十三億人都驚呆了。竟然有如此漂亮的方法!於是大陸人立刻仔細看了論文,並實作了這個演算法。結果,不實作還好,寫完一計時,居然比普通的$O(\log C)$演算法還慢!

為了,大陸人決定先從區間極值問題(RMQ)下手,試著讓$O(1)$還是比$O(\log N)$(zkw線段樹)快……

Input Format

本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。

#include "lib1965.h"之後實作下列函數,如果你的函數名稱不對或者長得不像下面那行,你將會獲得一個CE。
void init(int N, uint64_t C[]);:傳入一個長度為$N$的整數陣列$C_0, C_1, \cdots, C_{N-1}$。為了大陸人實作方便,保證C中的元素兩兩不相同。
uint64_t RMQ(int a, int b);:本函數必須回傳$C_a, C_{a+1}, \cdots, C_{b-1}$所有元素之中的最大值是多少。保證$0\leq a<b\leq N$。

對於所有的測資,$N\leq 10^ 7, Q\leq 3\times 10^ 7$,其中$Q$是呼叫RMQ的次數。
對於27%的測資,$N\leq 10^ 6, Q\leq 10^ 6$。

一次執行當中,init函數只會被呼叫一次。

注意:如果你在程式裡實作了main()函式,你也會獲得一個CE。

Output Format

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

Sample Input

Sample Output

Hints


如果你想要獲得滿分的話,你可能要試著動態開記憶體。

Problem Source

Judge / Description by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 4
For Testdata: 2 ~ 4, Score: 23
For Testdata: 5 ~ 7, Score: 37
For Testdata: 2 ~ 9, Score: 33
For Testdata: 0 ~ 1, Score: 3
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2900 102400 65536
1 1900 65536 65536
2 900 768432 65536
3 900 768432 65536
4 900 768432 65536
5 17000 1048576 65536
6 17000 1048576 65536
7 17000 1048576 65536
8 5900 768432 65536
9 5900 768432 65536