TopCoder

User's AC Ratio

89.3% (25/28)

Submission's AC Ratio

34.1% (45/132)

Description

現在你有一個長度為N的正整數序列$D_0, D_1, \cdots , D_{N-1}$。
你會接到M個包含a, b, k三個正整數的change請求($0 \leq a \leq b < N$),要求你把$D_a, D_{a+1}, \cdots , D_b$中的「第偶數項」全部加上k,「第奇數項」則全部減掉k。
注意:$D_a$算是第1項,因此是「第奇數項」。例如原本的序列為2, 3, 7, 9, 8, 5,當請求$(a, b, k) = (2, 4, 3)$時,改變後的序列為2, 3, 4, 12, 5, 5。)
接下來,你會需要回答Q次序列中的某一項的數值。

Input Format

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

#include "lib1227.h"之後實作下列三個函數。

void init(int N, long long D[]);:評測系統將會在執行的一開始呼叫這個函式,傳入正整數序列的長度N,以及長度為N的正整數陣列D。
void change(int a, int b, long long k);:呼叫完init後,將會連續呼叫M次這個函式,傳入正整數a, b, k。關於這項操作,請詳閱題目敘述。
long long query(int c);:呼叫完M次change後,將會連續呼叫Q次這個函式,傳入正整數c,你需要回傳序列中第c項的數值。

如果你的函數名稱不對或者長得不像上面那幾行,你將會獲得一個CE。
注意:如果你在程式裡實作了main()函式,你也會獲得一個CE。

保證數字在運算過程中,絕對不會超出long long範圍(overflow)。
對於所有的測資,$N,M,Q \leq 10^ 6$。

子任務(測資) 額外限制 分數
1 (0~1) $M=0$ 1
2 (2~5) $N,M \leq 5 \times 10^ 3$ 14
3 (6~9) 對於每一次change的呼叫,$b-a \leq 2$ 15
4 (10~12) 27
5 (13~15) 43

Output Format

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

Sample Input

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
10 4 4
1 2 3 4 5 6 7 8 9 10
0 9 0
1 4 2
3 8 1
5 6 4
1
3
5
7

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
0
1
1
7

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:N, M, Q;
第二行:$D_0, D_1, \cdots , D_{N-1}$;
接下來M行:a, b, k;
接下來Q行:c;
對於每一次呼叫query函數,此程式會輸出函數回傳的數值。

以下是一個保證格式正確(不會CE也不會REMLE)但只能讓你獲得1分的範例程式:
#include "lib1227.h"

long long* D;
int N;

void init(int n, long long d[])
{

N = n;
D = d;
}

void change(int a, int b, long long k)
{

D[N - 1] = 0;
}

long long query(int c)
{

return D[c];
}

Problem Source

Judge / Description by Yihda Yol
建國中學105學年度校隊選拔:複試pA

Subtasks

For Testdata: 0 ~ 1, Score: 1
For Testdata: 2 ~ 5, Score: 14
For Testdata: 6 ~ 9, Score: 15
For Testdata: 10 ~ 12, Score: 27
For Testdata: 13 ~ 15, Score: 43
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 65536
1 1000 131072 65536
2 1000 131072 65536
3 1000 131072 65536
4 1000 131072 65536
5 1000 131072 65536
6 2000 131072 65536
7 2000 131072 65536
8 2000 131072 65536
9 2000 131072 65536
10 4000 131072 65536
11 4000 131072 65536
12 4000 131072 65536
13 500 32768 65536
14 500 32768 65536
15 500 32768 65536