結果

問題 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
ユーザー 👑 ygussanyygussany
提出日時 2020-10-24 20:10:49
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 1,339 bytes
コンパイル時間 1,239 ms
コンパイル使用メモリ 30,940 KB
実行使用メモリ 262,212 KB
最終ジャッジ日時 2023-09-28 20:44:29
合計ジャッジ時間 3,998 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 0 ms
4,380 KB
testcase_05 AC 0 ms
4,380 KB
testcase_06 AC 0 ms
4,380 KB
testcase_07 AC 0 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 95 ms
208,052 KB
testcase_12 AC 88 ms
166,844 KB
testcase_13 AC 120 ms
245,984 KB
testcase_14 AC 65 ms
183,548 KB
testcase_15 AC 39 ms
122,624 KB
testcase_16 AC 43 ms
107,076 KB
testcase_17 AC 13 ms
47,172 KB
testcase_18 AC 76 ms
187,240 KB
testcase_19 AC 68 ms
192,624 KB
testcase_20 AC 43 ms
128,880 KB
testcase_21 AC 126 ms
262,212 KB
testcase_22 AC 125 ms
262,032 KB
testcase_23 AC 126 ms
262,092 KB
testcase_24 AC 0 ms
4,376 KB
testcase_25 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int Mod = 998244353;

void merge_sort(int x[], int n)
{
	static int y[6003] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p] < x[q])? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, Q, A[6003];
	scanf("%d %d", &N, &Q);
	for (i = 1, A[0] = 0, A[N+1] = 1 << 30; i <= N; i++) scanf("%d", &(A[i]));
	merge_sort(A, N + 2);

	int j, k, l, m[2], r, p, q;
	long long ans, tmp, coeff[6001][6001];
	for (i = N - 1, coeff[N][0] = A[N] - 1, coeff[N][1] = 1; i >= 1; i--) {
		for (j = 0, coeff[i][0] = 0; j <= N - i; j++) {
			coeff[i][j+1] = coeff[i+1][j];
			coeff[i][j] = (coeff[i][j] + coeff[i+1][j] * (A[i] - 1)) % Mod;
		}
	}
	for (q = 1; q <= Q; q++) {
		scanf("%d %d %d", &l, &r, &p);
		for (j = 1; A[j] < l; j++);
		for (k = j; A[k] < r; k++);
		
		ans = 0;
		for (i = 1, tmp = 1; i < j; i++) tmp = tmp * A[i] % Mod;
		for (; j <= k && N - j + 1 >= p; tmp = tmp * A[j++] % Mod) {
			m[0] = (l > A[j-1] + 1)? l: A[j-1] + 1;
			m[1] = (r < A[j])? r: A[j];
			if ((m[1] - m[0]) % 2 == 1) continue;
			ans ^= tmp * coeff[j][p] % Mod;
		}
		printf("%lld\n", ans % Mod);
	}
	
	fflush(stdout);
	return 0;
}
0