Submission #704958

#	Time	Username	Problem	Language	Result	Execution time	Memory
704958		MtSaka	Crossing (JOI21_crossing)	C++17	100 / 100	4014 ms	106928 KiB

Main

#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;
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';
}
vector<string>v;
vector sum(3,vector(9,vector<ll>()));
struct segment_tree{
  private:
  int n,id,sz,lg;
  vector<ll>seg;
  vector<int>lazy;
  void eval(int k,int l,int r){
    if(lazy[k]!=-1){
      seg[k]=sum[lazy[k]][id][min(n,r)]-sum[lazy[k]][id][l];
      if(r-l>1)lazy[k<<1]=lazy[k],lazy[k<<1|1]=lazy[k];
    }
    lazy[k]=-1;
  }
  void update(int i){
    seg[i]=seg[i<<1]+seg[i<<1|1];
  }
  public:
  segment_tree()=default;
  segment_tree(string s,int id):n(s.size()),id(id){
    sz=1,lg=0;
    while(sz<n)sz<<=1,lg++;
    seg.resize(sz<<1);
    rep(i,0,n){
      seg[i+sz]=(s[i]!=v[id][i]);
    }
    rrep(i,1,sz)update(i);
    lazy.assign(sz<<1,-1);
  }
  void apply(int l,int r,int a,int id=1,int l1=0,int r1=-1){
    if(r1<0)r1=sz;
    eval(id,l1,r1);
    if(r<=l1||r1<=l)return;
    if(l<=l1&&r1<=r){
      lazy[id]=a;
      eval(id,l1,r1);
    }
    else{
      apply(l,r,a,id<<1,l1,(l1+r1)>>1);
      apply(l,r,a,id<<1|1,(l1+r1)>>1,r1);
      update(id);
    }
  }
  int prod(int l,int r,int id=1,int l1=0,int r1=-1){
    if(r1<0)r1=sz;
    if(r1<=l||r<=l1)return 0;
    eval(id,l1,r1);
    if(l<=l1&&r1<=r)return seg[id];
    return prod(l,r,id<<1,l1,(l1+r1)>>1)+prod(l,r,id<<1|1,(l1+r1)>>1,r1);
  }
};
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);
  int n;cin>>n;
  string a,b,c;cin>>a>>b>>c;
  v.emplace_back(a);
  v.emplace_back(b);
  v.emplace_back(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);
  v.emplace_back(ab);
  v.emplace_back(bc);
  v.emplace_back(ac);
  v.emplace_back(abbc);
  v.emplace_back(abac);
  v.emplace_back(bcac);
  rep(i,0,9){
    rep(j,0,3)sum[j][i].resize(n+1);
    rep(j,0,n){
      rep(k,0,3)if(get_id(v[i][j])!=k)sum[k][i][j+1]=1;
    }
    rep(j,0,n){
      sum[0][i][j+1]+=sum[0][i][j];
      sum[1][i][j+1]+=sum[1][i][j];
      sum[2][i][j+1]+=sum[2][i][j];
    }
  }
  int q;cin>>q;
  string t;cin>>t;
  vector<segment_tree>seg(9);
  auto calc=[&]()->bool {
    rep(i,0,9)if(seg[i].prod(0,n)==0)return true;
    return false;
  };
  rep(i,0,9)seg[i]=segment_tree(t,i);
  if(calc()){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
  rep(i,0,q){
    int l,r;char c;
    cin>>l>>r>>c;
    l--;
    rep(j,0,9)seg[j].apply(l,r,get_id(c));
    //cerr<<seg.all_prod()<<endl;
    if(calc()){
      cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
  }
}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51