oj.uz

Submission #705064

# Submission time Handle Problem Language Result Execution time Memory
705064 2023-03-03T10:24:25 Z MtSaka Crossing (JOI21_crossing) C++17
0 / 100
 344 ms 8784 KB 
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
using ll=long long;
using namespace std;
using ull=unsigned long long;
vector<ull>pw(400000),pw2(400000);
static constexpr ull MOD=(1LL<<61)-1;
static constexpr ull inv2=(1LL<<60);
static constexpr ull base=2199866433;
ull mul(ull a,ull b){
  return __uint128_t(a)*b%MOD;
}
ull add(ull a,ull b){
  a+=b;if(a>=MOD)a-=MOD;
  return a;
}
ull div2(ull a){
  return mul(a,inv2);
}
void init(){
  pw[0]=1;
  rep(i,1,pw.size())pw[i]=mul(base,pw[i-1]);
  pw2[0]=0;
  rep(i,1,pw2.size())pw2[i]=pw2[i-1]+pw[i-1];
}
int get_id(char c){
  if(c=='J')return 0;
  if(c=='O')return 1;
  return 2;
}
char from_id(int a){
  if(a==0)return 'J';
  if(a==1)return 'O';
  return 'I';
}
struct segment_rolling_hash{
  private:
  int n,sz,lg;
  vector<pair<ull,ll>>seg;
  vector<int>lazy;
  void all_apply(int k,int a){
    seg[k].first=mul(from_id(a),pw2[seg[k].second]);
    if(k<sz)lazy[k]=a;
  }
  void push(int k){
    if(lazy[k]==-1)return;
    all_apply(k<<1,lazy[k]);all_apply(k<<1|1,lazy[k]);
    lazy[k]=-1;
  }
  void update(int i){
    seg[i].first=add(mul(seg[i<<1].first,pw[seg[i<<1|1].second]),seg[i<<1|1].first);
    seg[i].second=seg[i<<1].second+seg[i<<1|1].second;
  }
  public:
  segment_rolling_hash(string s):n(s.size()){
    sz=1,lg=0;
    while(sz<n)sz<<=1,lg++;
    seg.resize(sz<<1);
    rep(i,0,n){
      seg[i+sz].second=1;
      seg[i+sz].first=s[i];
    }
    rrep(i,1,sz)update(i);
    lazy.assign(sz,-1);
  }
  void apply(int l,int r,int a){
    l+=sz,r+=sz;
   rrep(i,1,lg+1){
      if(((l>>i)<<i)!=l)push(l>>i);
      if(((r>>i)<<i)!=r)push((r-1)>>i);
    }
    for(int l2=l,r2=r;l2<r2;l2>>=1,r2>>=1){
      if(l2&1)all_apply(l2++,a);
      if(r2&1)all_apply(--r2,a);
    }
    rep(i,0,lg+1){
      if(((l>>i)<<i)!=l)update(l>>i);
      if(((r>>i)<<i)!=r)update((r-1)>>i);
    }
  }
  ull all_prod()const{return seg[1].first;}
};
ull get_hash(string a){
  ull hash=0;
  for(auto i:a){
    hash=mul(hash,base);
    hash=add(hash,i);
  }
  return hash;
}
string f(string a,string b){
  assert(a.size()==b.size());
  string ans(a.size(),'1');
  rep(i,0,a.size()){
    if(get_id(a[i])==get_id(b[i]))ans[i]=a[i];
    else ans[i]=from_id(3^get_id(a[i])^get_id(b[i]));
  }
  return ans;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  init();
  int n;cin>>n;
  string a,b,c;cin>>a>>b>>c;
  //cerr<<a<<" "<<b<<" "<<c<<endl;
  string ab=f(a,b),bc=f(b,c),ac=f(a,c),abbc=f(ab,bc),abac=f(ab,ac),bcac=f(bc,ac);
  //cerr<<ab<<" "<<bc<<" "<<ac<<endl;
  //cerr<<abbc<<" "<<abac<<" "<<bcac<<endl;
  set<ull>st;
  st.insert(get_hash(a));
  st.insert(get_hash(b));
  st.insert(get_hash(c));
  st.insert(get_hash(ab));
  st.insert(get_hash(bc));
  st.insert(get_hash(ac));
  st.insert(get_hash(abbc));
  st.insert(get_hash(abac));
  st.insert(get_hash(bcac));
  //for(auto i:st)cerr<<i<<endl;
  int q;cin>>q;
  string t;cin>>t;
  segment_rolling_hash seg(t);
  if(st.count(seg.all_prod())){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
  rep(i,0,q){
    int l,r;char c;
    cin>>l>>r>>c;
    l--;
    seg.apply(l,r,get_id(c));
    //cerr<<seg.all_prod()<<endl;
    if(st.count(seg.all_prod())){
      cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
  }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 8524 KB Output is correct
2 Correct 320 ms 8668 KB Output is correct
3 Correct 315 ms 8564 KB Output is correct
4 Correct 344 ms 8724 KB Output is correct
5 Correct 292 ms 8624 KB Output is correct
6 Correct 304 ms 8596 KB Output is correct
7 Correct 305 ms 8552 KB Output is correct
8 Correct 307 ms 8612 KB Output is correct
9 Correct 317 ms 8680 KB Output is correct
10 Correct 306 ms 8764 KB Output is correct
11 Correct 326 ms 8636 KB Output is correct
12 Correct 311 ms 8764 KB Output is correct
13 Correct 339 ms 8648 KB Output is correct
14 Correct 313 ms 8628 KB Output is correct
15 Correct 319 ms 8784 KB Output is correct
16 Correct 337 ms 8636 KB Output is correct
17 Correct 340 ms 8680 KB Output is correct
18 Incorrect 317 ms 8540 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 8524 KB Output is correct
2 Correct 320 ms 8668 KB Output is correct
3 Correct 315 ms 8564 KB Output is correct
4 Correct 344 ms 8724 KB Output is correct
5 Correct 292 ms 8624 KB Output is correct
6 Correct 304 ms 8596 KB Output is correct
7 Correct 305 ms 8552 KB Output is correct
8 Correct 307 ms 8612 KB Output is correct
9 Correct 317 ms 8680 KB Output is correct
10 Correct 306 ms 8764 KB Output is correct
11 Correct 326 ms 8636 KB Output is correct
12 Correct 311 ms 8764 KB Output is correct
13 Correct 339 ms 8648 KB Output is correct
14 Correct 313 ms 8628 KB Output is correct
15 Correct 319 ms 8784 KB Output is correct
16 Correct 337 ms 8636 KB Output is correct
17 Correct 340 ms 8680 KB Output is correct
18 Incorrect 317 ms 8540 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 8524 KB Output is correct
2 Correct 320 ms 8668 KB Output is correct
3 Correct 315 ms 8564 KB Output is correct
4 Correct 344 ms 8724 KB Output is correct
5 Correct 292 ms 8624 KB Output is correct
6 Correct 304 ms 8596 KB Output is correct
7 Correct 305 ms 8552 KB Output is correct
8 Correct 307 ms 8612 KB Output is correct
9 Correct 317 ms 8680 KB Output is correct
10 Correct 306 ms 8764 KB Output is correct
11 Correct 326 ms 8636 KB Output is correct
12 Correct 311 ms 8764 KB Output is correct
13 Correct 339 ms 8648 KB Output is correct
14 Correct 313 ms 8628 KB Output is correct
15 Correct 319 ms 8784 KB Output is correct
16 Correct 337 ms 8636 KB Output is correct
17 Correct 340 ms 8680 KB Output is correct
18 Incorrect 317 ms 8540 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 8524 KB Output is correct
2 Correct 320 ms 8668 KB Output is correct
3 Correct 315 ms 8564 KB Output is correct
4 Correct 344 ms 8724 KB Output is correct
5 Correct 292 ms 8624 KB Output is correct
6 Correct 304 ms 8596 KB Output is correct
7 Correct 305 ms 8552 KB Output is correct
8 Correct 307 ms 8612 KB Output is correct
9 Correct 317 ms 8680 KB Output is correct
10 Correct 306 ms 8764 KB Output is correct
11 Correct 326 ms 8636 KB Output is correct
12 Correct 311 ms 8764 KB Output is correct
13 Correct 339 ms 8648 KB Output is correct
14 Correct 313 ms 8628 KB Output is correct
15 Correct 319 ms 8784 KB Output is correct
16 Correct 337 ms 8636 KB Output is correct
17 Correct 340 ms 8680 KB Output is correct
18 Incorrect 317 ms 8540 KB Output isn't correct
19 Halted 0 ms 0 KB -