#1020957 (C) No.2942 Sigma Music Game Level Problem

• 問題: No.2942 Sigma Music Game Level Problem
• ユーザー: pengin_2000
• 提出日時: 2024-10-18 23:28:34
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 685 ms / 6,000 ms
• コード長: 1,335 bytes
• コンパイル時間: 1,716 ms
• コンパイル使用メモリ: 30,720 KB
• 実行使用メモリ: 25,728 KB
• 最終ジャッジ日時: 2024-11-15 20:21:31
• 合計ジャッジ時間: 11,303 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5 ms; 10,112 KB
testcase_01	AC	5 ms; 9,856 KB
testcase_02	AC	4 ms; 10,112 KB
testcase_03	AC	4 ms; 10,112 KB
testcase_04	AC	4 ms; 10,112 KB
testcase_05	AC	4 ms; 10,112 KB
testcase_06	AC	4 ms; 10,112 KB
testcase_07	AC	4 ms; 9,984 KB
testcase_08	AC	5 ms; 10,112 KB
testcase_09	AC	4 ms; 10,112 KB
testcase_10	AC	5 ms; 10,112 KB
testcase_11	AC	264 ms; 16,512 KB
testcase_12	AC	607 ms; 21,632 KB
testcase_13	AC	584 ms; 18,560 KB
testcase_14	AC	290 ms; 18,048 KB
testcase_15	AC	216 ms; 17,280 KB
testcase_16	AC	536 ms; 17,408 KB
testcase_17	AC	121 ms; 13,312 KB
testcase_18	AC	380 ms; 16,640 KB
testcase_19	AC	685 ms; 20,608 KB
testcase_20	AC	182 ms; 15,104 KB
testcase_21	AC	569 ms; 25,728 KB
testcase_22	AC	550 ms; 25,600 KB
testcase_23	AC	213 ms; 13,184 KB
testcase_24	AC	4 ms; 10,112 KB
testcase_25	AC	4 ms; 9,984 KB
testcase_26	AC	509 ms; 25,728 KB

ソースコード

#include<stdio.h>
long long int seg[2][1000006], ss;
void update(long long int z, long long int x, long long int d)
{
	x += ss - 1;
	seg[z][x] += d;
	while (x > 0)
	{
		x = (x - 1) / 2;
		seg[z][x] = seg[z][2 * x + 1] + seg[z][2 * x + 2];
	}
	return;
}
long long int get(long long int z, long long int l, long long int r)
{
	l += ss - 1;
	r += ss - 1;
	long long int res = 0;
	while (l < r)
	{
		if (l % 2 == 0)
			res += seg[z][l];
		l /= 2;
		if (r % 2 > 0)
			res += seg[z][r];
		r = r / 2 - 1;
	}
	if (l == r)
		res += seg[z][l];
	return res;
}
long long int L[1000006];
long long int a[1000006];
int main()
{
	long long int n, q;
	scanf("%lld %lld %lld", &n, &q, &L[0]);
	long long int i;
	for (i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	for (ss = 1; ss < 200005; ss *= 2);
	for (i = 0; i < 2 * ss - 1; i++)
		seg[0][i] = seg[1][i] = 0;
	for (i = 0; i < n; i++)
	{
		update(0, a[i], 1);
		update(1, a[i], a[i]);
	}
	long long int t, l, r, cnt = 0;
	for (i = 1; i <= q; i++)
	{
		L[i] = L[i - 1];
		scanf("%lld", &t);
		if (t == 1)
		{
			scanf("%lld", &l);
			update(0, l, 1);
			update(1, l, l);
		}
		else if (t == 2)
		{
			scanf("%lld %lld", &l, &r);
			printf("%lld %lld\n", get(0, l, r), get(1, l, r));
			cnt++;
		}
		else
		{
			scanf("%lld", &l);
			L[i] = l;
		}
	}
	if (cnt == 0)
		printf("Not Found!\n");
	return 0;
}