結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー bal4u
提出日時 2020-02-29 22:13:08
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 2,034 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 7,276 KB
最終ジャッジ日時 2024-10-13 20:20:33
合計ジャッジ時間 3,260 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]);
	}
}

typedef int INT;

// bit木 1-indexedに注意
// b[1..bw) に対して b[i] += v
void add(INT *b, int bw, int i, INT v) {
    while (i <= bw) b[i] += v, i += i & -i;
}

// b[1..bw) に対して b[i]++
void add1(INT *b, int bw, int i) {
    while (i <= bw) b[i]++, i += i & -i;
}

// b[1..bw) に対して sum(b[1]..b[i])
INT sum(int *b, int i) {
    INT s = 0;
    while (i > 0) s += b[i], i -= i & -i;
    return s;
}

#define MAX 200005
int bitn;
INT bitb[MAX], bitc[MAX];

// range_add: add x to [i,j)
void range_add(int i, int j, INT x) {
    add(bitb, bitn, i, -i*x), add(bitb, bitn, j, j*x);
    add(bitc, bitn, i, x),    add(bitc, bitn, j, -x);
}
void range_add1(int i, int j) {
    add(bitb, bitn, i, -i), add(bitb, bitn, j, j);
    add1(bitc, bitn, i),    add(bitc, bitn, j, -1);
}

// range_sum0: sum [0,i)
INT range_sum0(int i) {
    return sum(bitb, i) + sum(bitc, i)*i;
}
// range_sum: sum [i,j)
INT range_sum(int i, int j) {
    return range_sum0(j) - range_sum0(i);
}

#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 = 1; i <= N; ++i) A[i] = in();
	for (i = 0; i < Q; ++i) {
		C[i] = (gc() == 'B'), gc();
		X[i] = in(), Y[i] = in();
	}
	bitn = N+1;
	while (Q--) {
		if (C[Q]) range_add1(X[Q], Y[Q]+1);
		else B[X[Q]] += (ll)Y[Q] * range_sum(X[Q], X[Q]+1);
	}

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