結果

問題 No.1000 Point Add and Array Add
ユーザー bal4ubal4u
提出日時 2020-02-29 20:22:19
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 2,193 bytes
コンパイル時間 1,436 ms
コンパイル使用メモリ 30,512 KB
実行使用メモリ 9,924 KB
最終ジャッジ日時 2023-08-03 23:11:04
合計ジャッジ時間 5,633 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,688 KB
testcase_01 AC 1 ms
5,736 KB
testcase_02 AC 2 ms
5,668 KB
testcase_03 AC 2 ms
5,740 KB
testcase_04 AC 1 ms
5,696 KB
testcase_05 AC 1 ms
5,760 KB
testcase_06 AC 1 ms
5,664 KB
testcase_07 AC 1 ms
5,700 KB
testcase_08 AC 2 ms
5,816 KB
testcase_09 AC 1 ms
5,704 KB
testcase_10 AC 2 ms
5,692 KB
testcase_11 AC 2 ms
5,668 KB
testcase_12 AC 2 ms
5,856 KB
testcase_13 AC 2 ms
5,816 KB
testcase_14 AC 2 ms
5,732 KB
testcase_15 AC 2 ms
5,720 KB
testcase_16 AC 148 ms
9,516 KB
testcase_17 AC 115 ms
7,928 KB
testcase_18 AC 221 ms
9,920 KB
testcase_19 AC 223 ms
9,812 KB
testcase_20 AC 149 ms
9,812 KB
testcase_21 AC 242 ms
8,332 KB
testcase_22 AC 174 ms
9,924 KB
testcase_23 AC 239 ms
9,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yuki 1000 Point Add and Array Add
// 2020.2.28 bal4u

#include <stdio.h>

typedef long long ll;

int getchar_unlocked(void);
int putchar_unlocked();
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

int in() {  // 整数の入力
	int n = 0; int c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(ll n)
{
	int i;
	char ob[40];

	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) ob[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(ob[i]);
	}
}

// セグメント木
#define MAXN (1<<18)      // セグメント木のサイズ。2のべき乗にすべし

int size;
int segVal[2 * MAXN];
int segLazy[2 * MAXN];

void segInit(int n) {
	size = 1; while (size < n) size <<= 1;
//	memset(segVal, 0, sizeof(segVal));
//  memset(segLazy, 0, sizeof(segLazy));
}

void lazy(int k, int width) {
	int k2 = k << 1;
	if (k2 < (size << 1) - 2) {
		segLazy[k2 + 1] += segLazy[k];
		segLazy[k2 + 2] += segLazy[k];
	}
	segVal[k] += segLazy[k] * width;
	segLazy[k] = 0;
}

int add(int a, int b, int x, int k, int l, int r) {
	int ans;

	lazy(k, r - l);
	if (r <= a || b <= l) return segVal[k] + segLazy[k] * (r - l);
	if (a <= l && r <= b) {
		segLazy[k] += x;
		return segVal[k] + segLazy[k] * (r - l);
	}
	lazy(k, r - l);
	ans = add(a, b, x, (k << 1) + 1, l, (l + r) >> 1);
	ans += add(a, b, x, (k << 1) + 2, (l + r) >> 1, r);
	return segVal[k] = ans;
}

int val(int a, int k, int l, int r) {
	int ans;

	lazy(k, r - l);
	if (r <= a || a+1 <= l) return 0;
	if (a <= l && r <= a+1) return segVal[k];
	ans = val(a, (k << 1) + 1, l, (l + r) >> 1);
	ans += val(a, (k << 1) + 2, (l + r) >> 1, r);
	return ans;
}

#define MAX 200005
char C[MAX]; int X[MAX], Y[MAX];
int A[MAX];
ll B[MAX];

int main()
{
	int i, N, Q;

	N = in(), Q = in();
	for (i = 0; i < N; ++i) A[i] = in();
	for (i = 0; i < Q; ++i) {
		C[i] = (gc() == 'B'), gc();
		X[i] = in()-1, Y[i] = in();
	}
	segInit(N);
	while (Q--) {
		if (C[Q]) add(X[Q], Y[Q], 1, 0, 0, N);
		else B[X[Q]] += (ll)Y[Q] * val(X[Q], 0, 0, N);
	}

	out(B[0] + (ll)A[0] * val(0, 0, 0, N));
	for (i = 1; i < N; ++i) {
		pc(' ');
		out(B[i] + (ll)A[i] * val(i, 0, 0, N));
	}
	pc('\n');
	return 0;
}
0