結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー やまぞうやまぞう
提出日時 2015-04-12 01:12:45
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,733 bytes
コンパイル時間 490 ms
コンパイル使用メモリ 64,356 KB
実行使用メモリ 5,632 KB
最終ジャッジ日時 2024-07-04 13:55:06
合計ジャッジ時間 18,291 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 846 ms
5,504 KB
testcase_01 AC 4,365 ms
5,632 KB
testcase_02 TLE -
testcase_03 AC 803 ms
5,632 KB
testcase_04 AC 4,315 ms
5,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <climits>
#include <fstream>

using namespace std;

typedef unsigned int UINT;
typedef unsigned long long ULONGLONG;

#define UINT_BIT (CHAR_BIT * sizeof(UINT))
#define UPDIV(x, n) (((x) + (n) - 1) / (n))

#define MAX_N 2000000

char result[MAX_N + 1];

int main()
{
#if 0
	ifstream in("test_in/in1");
	ofstream out("temp_1.txt");
#else
#define in cin
#define out cout
#endif

	UINT N, S, X, Y, Z;
	in >> N >> S >> X >> Y >> Z;
	vector<UINT> A, B;
	A.resize(UPDIV(N, UINT_BIT));
	B.resize(UPDIV(N, UINT_BIT));

	ULONGLONG a = S;
	for (UINT i = 0; i < N; i++) {
		A[i / UINT_BIT] |= (a & 1) << (i % UINT_BIT);
		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;
		s--;
		t--;
		u--;
		v--;

		UINT t_idx = t / UINT_BIT;
		UINT t_off = t % UINT_BIT;
		UINT v_idx = v / UINT_BIT;
		UINT v_off = v % UINT_BIT;
		for (UINT i = s / UINT_BIT; i <= t_idx; i++) {
			B[i] = A[i];
		}

		while (s <= t) {
			UINT s_idx = s / UINT_BIT;
			UINT s_off = s % UINT_BIT;
			UINT u_idx = u / UINT_BIT;
			UINT u_off = u % UINT_BIT;

			UINT w = B[s_idx] & (~0U << s_off);
			if (t_idx == s_idx) {
				w &= ~0U >> (UINT_BIT - t_off - 1);
			}
			if (s_off > u_off) {
				w >>= s_off - u_off;
				A[u_idx] ^= w;
				u += UINT_BIT - s_off;
				s += UINT_BIT - s_off;
			}
			else if (u_off > s_off) {
				w <<= u_off - s_off;
				A[u_idx] ^= w;
				s += UINT_BIT - u_off;
				u += UINT_BIT - u_off;
			}
			else {
				A[u_idx] ^= w;
				s += UINT_BIT - u_off;
				u += UINT_BIT - u_off;
			}
		}
	}
	for (UINT i = 0; i < N; i++) {
		result[i] = "EO"[(A[i / UINT_BIT] >> (i % UINT_BIT)) & 1];
	}
	result[N] = 0;
	out << result << endl;
}
0