結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー ゴリポン先生
提出日時 2025-10-11 10:19:11
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 3,752 ms / 5,000 ms
コード長 1,282 bytes
コンパイル時間 5,260 ms
コンパイル使用メモリ 199,204 KB
実行使用メモリ 20,952 KB
最終ジャッジ日時 2025-10-11 10:19:30
合計ジャッジ時間 19,336 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://kmjp.hatenablog.jp/entry/2015/02/02/0900 より
import std;

void main()
{
	// 入力
	long N, S, X, Y, Z, T, U, V;
	readln.chomp.formattedRead("%d %d %d %d %d", N, S, X, Y, Z);
	// 前処理
	auto A = S.recurrence!((a, n) => (X * a[n - 1] + Y) % Z).take(N).array;
	// A_iの下位1ビットを50桁ずつ保持する
	auto C = new long[](N / 50 + 2);
	foreach (i; 0 .. N)
		C[i / 50] |= (A[i] & 1) << (i % 50);
	// クエリの処理
	auto TT = new long[](2500);
	foreach (_; 0 .. readln.chomp.to!int) {
		readln.chomp.formattedRead("%d %d %d %d", S, T, U, V);
		long sp = T - S + 1;
		S--, U--;
		long x = S % 50;
		foreach (i; 0 .. sp / 50 + 2)
			TT[1 + i] = C[S / 50 + i];
		foreach (i; 0 .. sp / 50 + 2)
			TT[1 + i] = (TT[1 + i] >> x) | ((TT[i + 2] & ((1L << x) - 1)) << (50 - x));
		foreach (i; 0 .. sp / 50 + 4) {
			if ((i + 1) * 50 <= sp) continue;
			if ((i + 1) * 50 - sp <= 50)
				TT[i + 1] &= (1L << (sp % 50)) - 1;
			else
				TT[i + 1] = 0;
		}
		x = U % 50;
		foreach_reverse (i; 0 .. sp / 50 + 3)
			TT[i + 1] = ((TT[i + 1] << x) | (TT[i] >> (50 - x))) & ((1L << 50) - 1);
		foreach (i; 0 .. sp / 50 + 2)
			C[i + U / 50] ^= TT[i + 1];
	}
	// 答えの出力
	foreach (i; 0 .. N)
		write("EO"[(C[i / 50] >> (i % 50)) & 1]);
	writeln();
}
0