結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー なおなお
提出日時 2015-02-02 19:48:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,571 ms / 5,000 ms
コード長 2,642 bytes
コンパイル時間 1,252 ms
コンパイル使用メモリ 161,256 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2024-06-23 06:40:43
合計ジャッジ時間 7,369 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 308 ms
7,328 KB
testcase_01 AC 1,258 ms
7,328 KB
testcase_02 AC 1,571 ms
7,200 KB
testcase_03 AC 281 ms
7,200 KB
testcase_04 AC 1,156 ms
7,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
const int MOD = int(1e9+7);

struct bitarray{
    typedef unsigned long long elem;
    static const int es = sizeof(elem)*8;
    elem emask[es+1];
    int N,EN; elem *ar;
    bitarray(int N):N(N){
        EN=(N+es-1)/es+1;ar=new elem[EN]; memset(ar,0,EN*sizeof(elem));
        for(int i=0;i<=es;i++) emask[i]=(i==es)?-1:((elem)1<<i)-1;
    }
    inline void set(int n, bool f){
        if(n>=N) throw;
        int m=n%es;n/=es;
        ar[n] = (ar[n] & ~((elem)1 << m)) | ((elem)f << m);
    }
    inline bool get(int n) const{
        if(n>=N) throw;
        int m=n%es;n/=es;
        return (ar[n]>>m)&1;
    }
    inline elem getblock(int n) const {
        int m=n%es;n/=es;
        if(m) return (ar[n]>>m) | (ar[n+1]<<(es-m));
        return ar[n];
    }
    inline void setblock(int n, elem v, elem mask = -1){
        int m=n%es;n/=es; v &= mask;
        ar[n] = (ar[n] & ~(mask << m)) | (v << m);
        if(m) ar[n+1] = (ar[n+1] & ~(mask >> (es-m))) | (v >> (es-m));
    }

    void rangexor(int u, int v, int n){
        if(u < v && u+n > v){
            const int vend=v+n,uend=u+n;
            int bv=(vend-1)/es*es,bu=uend-(vend-bv);
            while(bv>=v){
                int bn=min(vend-bv,es);
                setblock(bv, getblock(bu)^getblock(bv), emask[bn]);
                bu-=es;bv-=es;n-=bn;
            }
            if(n){
                setblock(v, getblock(u)^getblock(v), emask[n]);
            }
        } else {
            int l=v-v/es*es,bv=v,bu=u;
            if(l){
                int bn=min(n,es-l);
                setblock(bv, getblock(bu)^getblock(bv), emask[bn]);
                bu+=bn;bv+=bn;n-=bn;
            }
            while(n){
                int bn=min(n,es);
                setblock(bv, getblock(bu)^getblock(bv), emask[bn]);
                bu+=bn;bv+=bn;n-=bn;
            }
        }
    }
};

int main(){
    do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0);

    int N,Q; ll S,X,Y,Z;
    cin >> N >> S >> X >> Y >> Z;

    bitarray ba(N);

    ll k = S;  
    ba.set(0,k&1);
    FOR(i,1,N) ba.set(i, (k = ((k*X)%Z+Y) % Z) & 1);

    cin >> Q;
    REP(i,Q){
        int s,t,u,v;
        cin >> s >> t >> u >> v;
        s--,u--;
        int n = t-s;
        ba.rangexor(s,u,n);
    }

    string res;
    REP(i,N) res += "EO"[ba.get(i)];
    cout << res << endl;
    return 0;
}
0