TopCoder

User's AC Ratio

55.0% (11/20)

Submission's AC Ratio

14.5% (91/629)

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

Hints


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

Problem Source

Judge / Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0 4
2 2~4 23
3 5~7 37
4 2~9 33
5 0~1 3

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2900 102400 262144 1 5
1 1900 65536 262144 5
2 1000 768432 262144 2 4
3 1000 768432 262144 2 4
4 1000 768432 262144 2 4
5 20000 1048576 262144 3 4
6 20000 1048576 262144 3 4
7 20000 1048576 262144 3 4
8 8800 768432 262144 4
9 8800 768432 262144 4