結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー やまぞう
提出日時 2015-04-11 22:51:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,807 bytes
コンパイル時間 487 ms
コンパイル使用メモリ 64,956 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 13:40:11
合計ジャッジ時間 17,586 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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];
            UINT m = ~0U << s_off;
            if (t_idx == s_idx) {
                m &= ~0U >> (UINT_BIT - t_off - 1);
            }
            if (s_off > u_off) {
                w >>= s_off - u_off;
                m >>= s_off - u_off;
                A[u_idx] ^= w & m;
                u += UINT_BIT - s_off;
                s += UINT_BIT - s_off;
            }
            else if (u_off > s_off) {
                w <<= u_off - s_off;
                m <<= u_off - s_off;
                A[u_idx] ^= w & m;
                s += UINT_BIT - u_off;
                u += UINT_BIT - u_off;
            }
            else {
                A[u_idx] ^= w & m;
                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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0