結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー bal4u
提出日時 2020-02-29 20:22:19
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 2,193 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2024-10-13 20:16:57
合計ジャッジ時間 3,549 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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