結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー eQeeQe
提出日時 2024-10-11 04:10:48
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,054 ms / 5,000 ms
コード長 5,709 bytes
コンパイル時間 5,647 ms
コンパイル使用メモリ 313,956 KB
実行使用メモリ 7,492 KB
最終ジャッジ日時 2024-10-11 04:11:02
合計ジャッジ時間 14,034 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 542 ms
7,492 KB
testcase_01 AC 1,708 ms
7,324 KB
testcase_02 AC 2,054 ms
7,328 KB
testcase_03 AC 542 ms
7,488 KB
testcase_04 AC 1,673 ms
7,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
namespace my{
void main();
void solve();
}
int main(){my::main();}
namespace my{
#define eb emplace_back
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define FO(n) for(ll ij=0;ij<n;++ij)
#define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i<i##stop;i+=i##step)
#define fo(i,...) FO##__VA_OPT__(R)(i __VA_OPT__(,__VA_ARGS__))
#define fe(a,i,...) for(auto&&__VA_OPT__([)i __VA_OPT__(,__VA_ARGS__]):a)
using namespace std;
using ll=int64_t;
using ull=uint64_t;
using ulll=__uint128_t;
istream&operator>>(istream&i,ulll&x){ull t;i>>t;x=t;return i;}
ostream&operator<<(ostream&o,const ulll&x){return(x<10?o:o<<x/10)<<ll(x%10);}
auto range(bool s,ll a,ll b=1e18,ll c=1){if(b==1e18)b=a,(s?b:a)=0;return array{a-s,b,c};}
constexpr char nl=10;
constexpr char sp=32;
constexpr ll log2_floor(auto x){x|=1;ll r=0;while(x>1)x>>=1,++r;return r;}
auto ceil(auto x,auto y){if(y<0)x=-x,y=-y;return x<=0?x/y:(x-1)/y+1;}

template<class V>concept vectorial=is_base_of_v<vector<typename V::value_type>,V>;
template<class V>istream&operator>>(istream&i,vector<V>&v){fe(v,e)i>>e;return i;}
template<class V>ostream&operator<<(ostream&o,const vector<V>&v){fe(v,e)o<<e<<string(&e!=&v.back(),vectorial<V>?nl:sp);return o;}

template<class V>struct vec:vector<V>{
  using vector<V>::vector;
  vec(const vector<V>&v){this->reserve(v.size());fe(v,e)this->eb(e);}

  vec&operator+=(const vec&u){vec&v=*this;fo(i,v.size())v[i]+=u[i];return v;}
  vec&operator-=(const vec&u){vec&v=*this;fo(i,v.size())v[i]-=u[i];return v;}
  vec&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;}
  vec operator+(const vec&u)const{return vec{*this}+=u;}
  vec operator-(const vec&u)const{return vec{*this}-=u;}
  vec operator^(const vec&u)const{return vec{*this}^=u;}
  vec&operator++(){fe(*this,e)++e;return*this;}
  vec&operator--(){fe(*this,e)--e;return*this;}
  vec operator-()const{vec v=*this;fe(v,e)e=-e;return v;}

  vec slice(ll l,ll r)const{return vec(this->begin()+l,this->begin()+r);}
};

void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);}
void lin(auto&...a){(cin>>...>>a);}
template<char c=sp>void pp(const auto&...a){ll n=sizeof...(a);((cout<<a<<string(--n>0,c)),...);cout<<nl;}

template<class T=uint64_t>struct dynamic_bitset{
  static constexpr size_t block_size=sizeof(T)*CHAR_BIT;
  static constexpr size_t block_index(size_t i){return i>>log2_floor(block_size);}
  static constexpr size_t bit_index(size_t i){return i&(block_size-1);}

  vec<T>bits;
  size_t n;
  size_t size()const{return n;}

  dynamic_bitset(size_t n):n(n),bits(ceil(n,block_size)){}
  dynamic_bitset(const string&s):n(s.size()),bits(ceil(s.size(),block_size)){fo(i,n)bits[block_index(i)]|=T(s[i]-'0')<<bit_index(i);}

  struct proxy{
    vec<T>&bits_proxy;
    size_t I;
    proxy(vec<T>&bits_proxy,size_t I):bits_proxy(bits_proxy),I(I){}
    auto&operator=(bool f){
      bits_proxy[block_index(I)]&=~(T(1)<<bit_index(I));
      bits_proxy[block_index(I)]|=T(f)<<bit_index(I);
      return*this;
    }
    template<integral X>auto&operator=(X x){return this->operator=(static_cast<bool>(x&1));}
    auto&operator=(const proxy&p){return this->operator=(static_cast<bool>(p));}
    operator bool()const{return bits_proxy[block_index(I)]>>bit_index(I)&1;}
  };

  decltype(auto)operator[](size_t i){return proxy{bits,i};}
  decltype(auto)operator[](size_t i)const{return bits[block_index(i)]>>bit_index(i)&1;}

  auto&operator&=(const dynamic_bitset&b){fo(i,bits.size())bits[i]&=b.bits[i];return*this;}
  auto&operator|=(const dynamic_bitset&b){fo(i,bits.size())bits[i]|=b.bits[i];return*this;}
  auto&operator^=(const dynamic_bitset&b){fo(i,bits.size())bits[i]^=b.bits[i];return*this;}
  auto operator&(const dynamic_bitset&b)const{return dynamic_bitset{*this}&=b;}
  auto operator|(const dynamic_bitset&b)const{return dynamic_bitset{*this}|=b;}
  auto operator^(const dynamic_bitset&b)const{return dynamic_bitset{*this}^=b;}

  auto slice(ll l,ll r)const{
    dynamic_bitset res(r-l);

    ll rem=bit_index(r-l);
    fo(rem){
      res[r-l-1]=(*this)[r-1];
      --r;
    }

    ll upper_shift=bit_index(l);
    ll lower_shift=block_size-upper_shift;
    ll n=block_index(r-l);
    ll start=block_index(l);
    fo(i,n){
      if(upper_shift==0)res.bits[i]=bits[start+i];
      else res.bits[i]=(bits[start+i]>>upper_shift)|(bits[start+i+1]<<lower_shift);
    }
    return res;
  }

  auto&range_bit_operation(const auto&op,ll l,const dynamic_bitset&p){
    ll r=l+p.size();

    ll rem=bit_index(r-l);
    fo(rem){
      (*this)[r-1]=op((*this)[r-1],p[r-l-1]);
      --r;
    }

    ll lower_shift=bit_index(l);
    ll upper_shift=block_size-lower_shift;
    ll n=block_index(r-l);
    ll start=block_index(l);
    fo(i,n){
      if(lower_shift==0)bits[start+i]=op(bits[start+i],p.bits[i]);
      else{
        bits[start+i]=op(bits[start+i],p.bits[i]<<lower_shift);
        bits[start+i+1]=op(bits[start+i+1],p.bits[i]>>upper_shift);
      }
    }
    return*this;
  }

  auto&range_xor(ll l,const dynamic_bitset&p){
    return range_bit_operation(bit_xor<>{},l,p);
  }

  string to_string()const{string s{};fo(i,size())s+=(*this)[i]+'0';return s;}
  friend istream&operator>>(istream&i,dynamic_bitset&db){string s;i>>s;db=s;return i;}
  friend ostream&operator<<(ostream&o,const dynamic_bitset&db){return o<<db.to_string();}
};

void main(){io();ll T=1;fo(T)solve();}
void solve(){
  LL(N,S,X,Y,Z);
  dynamic_bitset<ulll>a(N);
  a[0]=S;
  ll cu=S;
  fo(i,1,N){
    cu=(cu*X+Y)%Z;
    a[i]=cu;
  }

  LL(Q);
  fo(Q){
    LL(s,t,u,v);--s,--u;
    a.range_xor(u,a.slice(s,t));
  }

  string res{};
  fo(i,N)res+=(a[i]?'O':'E');
  pp(res);
}}
0