結果

問題 No.142 単なる配列の操作に関する実装問題
コンテスト
ユーザー やまぞう
提出日時 2015-04-14 01:57:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,376 ms / 5,000 ms
コード長 2,719 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 478 ms
コンパイル使用メモリ 62,868 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 14:22:26
合計ジャッジ時間 6,524 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <climits>
#include <fstream>
#include <cstdint>
using namespace std;

typedef unsigned int UINT;
typedef unsigned long long ULONGLONG;
typedef uint32_t DWORD;
typedef uint64_t QWORD;
#define MAKEQWORD(lo, hi) (QWORD(lo) | (QWORD(hi)<<32))
#define DWORD_BITS (CHAR_BIT * sizeof(DWORD))
#define INDEX(x) ((x) / (DWORD_BITS))
#define OFFSET(x) ((x) % (DWORD_BITS))
#define UPDIV(x, n) (((x) + (n) - 1) / (n))
#define MAX_N 2000000
DWORD ARR1[UPDIV(MAX_N, DWORD_BITS) + 2];
#define DATA(n) ARR1[(n) + 1]

int main()
{
#define in cin
#define out cout

	UINT N, S, X, Y, Z;
	in >> N >> S >> X >> Y >> Z;

	ULONGLONG a = S;
	for (UINT i = 0; i < N; i++) {
		DATA(INDEX(i)) |= (a & 1) << OFFSET(i);
		a = (X * a + Y) % Z;
	}
	UINT Q;
	in >> Q;
	for (UINT q = 0; q < Q; q++) {
		UINT S, T, U, V;
		in >> S >> T >> U >> V;
		UINT s = S - 1;
		UINT t = T - 1;
		UINT u = U - 1;
		UINT v = V - 1;

		QWORD w;
		if (u <= s) {
			if (INDEX(u) == INDEX(v)) {
				w = MAKEQWORD(DATA(INDEX(s)), DATA(INDEX(s) + 1)) >> OFFSET(s);
				w &= QWORD(~0U) >> (DWORD_BITS - (v - u + 1));
				w <<= OFFSET(u);
				DATA(INDEX(u)) ^= DWORD(w);
			}
			else {
				if (OFFSET(u) != 0) {
					w = MAKEQWORD(DATA(INDEX(s)), DATA(INDEX(s) + 1)) >> OFFSET(s);
					w <<= OFFSET(u);
					DATA(INDEX(u)) ^= DWORD(w);
					s += DWORD_BITS - OFFSET(u);
					u += DWORD_BITS - OFFSET(u);
				}
				while (INDEX(u) < INDEX(v)) {
					w = MAKEQWORD(DATA(INDEX(s)), DATA(INDEX(s) + 1)) >> OFFSET(s);
					DATA(INDEX(u)) ^= DWORD(w);
					s += DWORD_BITS;
					u += DWORD_BITS;
				}
				w = MAKEQWORD(DATA(INDEX(s)), DATA(INDEX(s) + 1)) >> OFFSET(s);
				w &= QWORD(~0U) >> (DWORD_BITS - (v - u + 1));
				w <<= OFFSET(u);
				DATA(INDEX(u)) ^= DWORD(w);
			}
		}
		else {
			if (INDEX(v) == INDEX(u)) {
				w = MAKEQWORD(DATA(INDEX(t) - 1), DATA(INDEX(t))) >> (OFFSET(t) + 1);
				w &= QWORD(~0U) << (DWORD_BITS - (v - u + 1));
				DATA(INDEX(v)) ^= DWORD(w) >> (DWORD_BITS - OFFSET(v) - 1);
			}
			else {
				if (OFFSET(v) != DWORD_BITS - 1) {
					w = MAKEQWORD(DATA(INDEX(t) - 1), DATA(INDEX(t)));
					w >>= (OFFSET(t) + 1);
					DATA(INDEX(v)) ^= DWORD(w) >> (DWORD_BITS - OFFSET(v) - 1);
					t -= OFFSET(v) + 1;
					v -= OFFSET(v) + 1;
				}
				while (INDEX(v) > INDEX(u)) {
					w = MAKEQWORD(DATA(INDEX(t) - 1), DATA(INDEX(t)));
					w >>= (OFFSET(t) + 1);
					DATA(INDEX(v)) ^= DWORD(w);
					t -= DWORD_BITS;
					v -= DWORD_BITS;
				}
				w = MAKEQWORD(DATA(INDEX(t) - 1), DATA(INDEX(t)));
				w >>= (OFFSET(t) + 1);
				w &= QWORD(~0U) << OFFSET(u);
				DATA(INDEX(v)) ^= DWORD(w);
			}
		}
	}
	for (UINT i = 0; i < N; i++) {
		out << "EO"[(DATA(INDEX(i)) >> OFFSET(i)) & 1];
	}
	out << endl;
}
0