oj.uz

Submission #704933

# Submission time Handle Problem Language Result Execution time Memory
704933 2023-03-03T06:57:49 Z MtSaka Crossing (JOI21_crossing) C++17
0 / 100
 340 ms 7632 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(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=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,base);
    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 287 ms 7072 KB Output is correct
2 Correct 311 ms 7216 KB Output is correct
3 Correct 317 ms 7132 KB Output is correct
4 Correct 311 ms 7116 KB Output is correct
5 Correct 315 ms 7036 KB Output is correct
6 Correct 286 ms 7048 KB Output is correct
7 Correct 306 ms 7128 KB Output is correct
8 Correct 302 ms 7132 KB Output is correct
9 Correct 310 ms 7080 KB Output is correct
10 Correct 314 ms 7160 KB Output is correct
11 Correct 315 ms 7104 KB Output is correct
12 Correct 331 ms 7120 KB Output is correct
13 Correct 301 ms 7148 KB Output is correct
14 Correct 340 ms 7108 KB Output is correct
15 Correct 304 ms 7116 KB Output is correct
16 Correct 309 ms 7108 KB Output is correct
17 Correct 326 ms 7632 KB Output is correct
18 Incorrect 309 ms 7568 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 7072 KB Output is correct
2 Correct 311 ms 7216 KB Output is correct
3 Correct 317 ms 7132 KB Output is correct
4 Correct 311 ms 7116 KB Output is correct
5 Correct 315 ms 7036 KB Output is correct
6 Correct 286 ms 7048 KB Output is correct
7 Correct 306 ms 7128 KB Output is correct
8 Correct 302 ms 7132 KB Output is correct
9 Correct 310 ms 7080 KB Output is correct
10 Correct 314 ms 7160 KB Output is correct
11 Correct 315 ms 7104 KB Output is correct
12 Correct 331 ms 7120 KB Output is correct
13 Correct 301 ms 7148 KB Output is correct
14 Correct 340 ms 7108 KB Output is correct
15 Correct 304 ms 7116 KB Output is correct
16 Correct 309 ms 7108 KB Output is correct
17 Correct 326 ms 7632 KB Output is correct
18 Incorrect 309 ms 7568 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 7072 KB Output is correct
2 Correct 311 ms 7216 KB Output is correct
3 Correct 317 ms 7132 KB Output is correct
4 Correct 311 ms 7116 KB Output is correct
5 Correct 315 ms 7036 KB Output is correct
6 Correct 286 ms 7048 KB Output is correct
7 Correct 306 ms 7128 KB Output is correct
8 Correct 302 ms 7132 KB Output is correct
9 Correct 310 ms 7080 KB Output is correct
10 Correct 314 ms 7160 KB Output is correct
11 Correct 315 ms 7104 KB Output is correct
12 Correct 331 ms 7120 KB Output is correct
13 Correct 301 ms 7148 KB Output is correct
14 Correct 340 ms 7108 KB Output is correct
15 Correct 304 ms 7116 KB Output is correct
16 Correct 309 ms 7108 KB Output is correct
17 Correct 326 ms 7632 KB Output is correct
18 Incorrect 309 ms 7568 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 7072 KB Output is correct
2 Correct 311 ms 7216 KB Output is correct
3 Correct 317 ms 7132 KB Output is correct
4 Correct 311 ms 7116 KB Output is correct
5 Correct 315 ms 7036 KB Output is correct
6 Correct 286 ms 7048 KB Output is correct
7 Correct 306 ms 7128 KB Output is correct
8 Correct 302 ms 7132 KB Output is correct
9 Correct 310 ms 7080 KB Output is correct
10 Correct 314 ms 7160 KB Output is correct
11 Correct 315 ms 7104 KB Output is correct
12 Correct 331 ms 7120 KB Output is correct
13 Correct 301 ms 7148 KB Output is correct
14 Correct 340 ms 7108 KB Output is correct
15 Correct 304 ms 7116 KB Output is correct
16 Correct 309 ms 7108 KB Output is correct
17 Correct 326 ms 7632 KB Output is correct
18 Incorrect 309 ms 7568 KB Output isn't correct
19 Halted 0 ms 0 KB -