TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

87.0% (40/46)

Submission's AC Ratio

19.8% (78/394)

Tags

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

本題沒有輸出。

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

No. Testdata Range Score
1 0~5 30
2 6 10
3 7~9 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 1
2 1000 131072 262144 1
3 1000 131072 262144 1
4 1000 131072 262144 1
5 1000 131072 262144 1
6 1000 131072 262144 2
7 2000 131072 262144 3
8 2000 131072 262144 3
9 2000 131072 262144 3