TopCoder

User's AC Ratio

88.6% (70/79)

Submission's AC Ratio

22.6% (140/620)

Tags

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 1

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見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 1

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見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

No. Testdata Range Score
1 0~1 1
2 2~5 14
3 6~9 15
4 10~12 27
5 13~15 43

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 2
3 1000 131072 262144 2
4 1000 131072 262144 2
5 1000 131072 262144 2
6 2000 131072 262144 3
7 2000 131072 262144 3
8 2000 131072 262144 3
9 2000 131072 262144 3
10 4000 131072 262144 4
11 4000 131072 262144 4
12 4000 131072 262144 4
13 500 32768 262144 5
14 500 32768 262144 5
15 500 32768 262144 5