TopCoder

Thumb 3ac79f3df8dcd1001410d90a738b4710b9122f08
矢澤にこ
にっこにっこにー♪ あなたのハートににこにこにー♪ 笑顔届ける矢澤にこにこー♪ にこにーって覚えてラブにこー♪

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

16.7% (53/317)

Description

※本題為互動題,請在程式碼中引入標頭檔:
#include "lib1871.h"

身為一名職業的扶他那裡控,もも落成了他的後宮“ふたなり(fu ta na li)幸福安心委員会“。
縱然職人もも面對各類扶他那裡(以下簡稱扶他)可說是身經百戰,但是面對這如海峽般的扶他數量對もも來說工作量還是太高了,因此你,天才扶他程式設計師,打算幫他分擔工作以作為平時受もも餵食的報答。

假設委員會裡總共有N名扶他,編號為0∼N−1,每名扶他的幸福度以A0,A1,…AN−1表示,那麼你的工作就是對於每筆もも的詢問(i,j),紀錄下i∼j中最不幸福的扶他的幸福度,好讓もも判斷是不是該將該名扶他斬首提醒該扶他好好履行她的義務。

請勿從stdin/out輸入輸出,否則會導致程式執行錯誤。
寫這題請務必引入表頭檔"lib1871.h",並使用下列函式作答:
1.int futa::init()
2. int* futa::momo_gives_you_list_of_futa()
3.int futa::momo_tells_you_q()
4.std::pair<int,int> futa::momo_asks()
5.void futa::you_tell_momo(int)

1.在做任何動作之前,請先呼叫函式futa::init(),該函式會返回一個正整數N代表總共有多少扶他。
2.接下來請呼叫函式futa::momo_gives_you_list_of_futa(),該函式會返回一個int* 指向一個大小N的陣列開頭,該陣列即為扶他幸福度陣列Ai,A[i]代表第i個扶他的幸福度。
3.再來請呼叫函式futa::momo_tells_you_q(),該函式會返回一個正整數q代表もも有q筆詢問。
4.再來要連續呼叫q次函式futa::momo_asks()futa::you_tell_momo(int)
futa::momo_asks()會返回一個pair代表一筆詢問(i,j),而你則用futa::you_tell_momo(int)返回該比詢問的答案。
在呼叫下一次的futa::momo_asks()之前請確實呼叫過futa::you_tell_momo(int)回報答案給もも否則你很有可能會WA。

Input Format

本題沒有輸入,請務必按照題目敘述的順序呼叫函式。

這是一段不一定會AC的範例code:

#include "lib1871.h"
#include <utility>

int main() {
  int n = futa::init();
  int *A = futa::momo_gives_you_list_of_futa();
  int q = futa::momo_tells_you_q();
  while (q--) {
    std::pair<int,int> a = futa::momo_asks();
    futa::you_tell_momo(A[a.first]);
  }
}

Output Format

本題沒有輸出。

Sample Input

Sample Output

Hints

※千萬不可在題目中由stdin/out進行輸入輸出

對於40%的測資:
你可以當作:   $1≤N≤10^ 4 $

對於所有測資:
你可以假設:   $1≤N≤10^ 6 $
你也可以這麼認為:$1≤q≤N $
你大可以選擇相信:$0≤A_ i≤2^ {32} −1 $
你必須接受:   對每筆詢問(i,j),$0≤i≤j≤N−1$

Problem Source

Step5

Subtasks

For Testdata: 0 ~ 5, Score: 30
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 9, Score: 60
No. Time Limit (ms) Memory Limit (KiB)
0 1000 131072
1 1000 131072
2 1000 131072
3 1000 131072
4 1000 131072
5 1000 131072
6 1000 131072
7 2000 131072
8 2000 131072
9 2000 131072