oj.uz

Submission #704926

# Submission time Handle Problem Language Result Execution time Memory
704926 2023-03-03T06:52:05 Z MtSaka Crossing (JOI21_crossing) C++17
0 / 100
 353 ms 4592 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);
static constexpr ull MOD=(1LL<<61)-1;
static constexpr ull inv2=(1LL<<60);
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]=add(add(pw[i-1],pw[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(a,div2(add(pw[seg[k].second],MOD-1)));
    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=get_id(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,3);
    hash=add(hash,get_id(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 4444 KB Output is correct
2 Correct 306 ms 4480 KB Output is correct
3 Correct 353 ms 4592 KB Output is correct
4 Correct 284 ms 4364 KB Output is correct
5 Correct 289 ms 4428 KB Output is correct
6 Correct 276 ms 4428 KB Output is correct
7 Correct 286 ms 4496 KB Output is correct
8 Correct 303 ms 4404 KB Output is correct
9 Correct 289 ms 4464 KB Output is correct
10 Correct 314 ms 4560 KB Output is correct
11 Correct 294 ms 4496 KB Output is correct
12 Correct 321 ms 4448 KB Output is correct
13 Correct 288 ms 4480 KB Output is correct
14 Correct 311 ms 4488 KB Output is correct
15 Correct 308 ms 4532 KB Output is correct
16 Incorrect 305 ms 4468 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 4444 KB Output is correct
2 Correct 306 ms 4480 KB Output is correct
3 Correct 353 ms 4592 KB Output is correct
4 Correct 284 ms 4364 KB Output is correct
5 Correct 289 ms 4428 KB Output is correct
6 Correct 276 ms 4428 KB Output is correct
7 Correct 286 ms 4496 KB Output is correct
8 Correct 303 ms 4404 KB Output is correct
9 Correct 289 ms 4464 KB Output is correct
10 Correct 314 ms 4560 KB Output is correct
11 Correct 294 ms 4496 KB Output is correct
12 Correct 321 ms 4448 KB Output is correct
13 Correct 288 ms 4480 KB Output is correct
14 Correct 311 ms 4488 KB Output is correct
15 Correct 308 ms 4532 KB Output is correct
16 Incorrect 305 ms 4468 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 4444 KB Output is correct
2 Correct 306 ms 4480 KB Output is correct
3 Correct 353 ms 4592 KB Output is correct
4 Correct 284 ms 4364 KB Output is correct
5 Correct 289 ms 4428 KB Output is correct
6 Correct 276 ms 4428 KB Output is correct
7 Correct 286 ms 4496 KB Output is correct
8 Correct 303 ms 4404 KB Output is correct
9 Correct 289 ms 4464 KB Output is correct
10 Correct 314 ms 4560 KB Output is correct
11 Correct 294 ms 4496 KB Output is correct
12 Correct 321 ms 4448 KB Output is correct
13 Correct 288 ms 4480 KB Output is correct
14 Correct 311 ms 4488 KB Output is correct
15 Correct 308 ms 4532 KB Output is correct
16 Incorrect 305 ms 4468 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 4444 KB Output is correct
2 Correct 306 ms 4480 KB Output is correct
3 Correct 353 ms 4592 KB Output is correct
4 Correct 284 ms 4364 KB Output is correct
5 Correct 289 ms 4428 KB Output is correct
6 Correct 276 ms 4428 KB Output is correct
7 Correct 286 ms 4496 KB Output is correct
8 Correct 303 ms 4404 KB Output is correct
9 Correct 289 ms 4464 KB Output is correct
10 Correct 314 ms 4560 KB Output is correct
11 Correct 294 ms 4496 KB Output is correct
12 Correct 321 ms 4448 KB Output is correct
13 Correct 288 ms 4480 KB Output is correct
14 Correct 311 ms 4488 KB Output is correct
15 Correct 308 ms 4532 KB Output is correct
16 Incorrect 305 ms 4468 KB Output isn't correct
17 Halted 0 ms 0 KB -