제출 #513179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513179		czhang2718	Crossing (JOI21_crossing)	C++17	100 / 100	2640 ms	355480 KiB

Main

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;

const int N=1000001;
const int no_op=-1;

int n, q;
string a, b, c, t;

struct segtree{
  int n;
  string s;
  int cnt[N][3];
  int good[N];
  int lazy[N];

  void build(int x, int lx, int rx){
    if(rx-lx==1){
      cnt[x][s[lx]-'0']=1;
      return;
    }
    int m=(lx+rx)/2;
    build(2*x+1, lx, m);
    build(2*x+2, m, rx);
    for(int i=0; i<3; i++){
      cnt[x][i]=cnt[2*x+1][i]+cnt[2*x+2][i];
    }
  }

  segtree(int n, string s){
    this->n=n, this->s=s;
    for(int i=0; i<4*n; i++){
      cnt[i][0]=cnt[i][1]=cnt[i][2]=0;
      good[i]=0;
      lazy[i]=no_op;
    }
    build(0, 0, n);
  }

  void push(int x, int lx, int rx){
    if(rx-lx==1 || lazy[x]==no_op) return;
    int v=lazy[x];
    good[2*x+1]=cnt[2*x+1][v];
    good[2*x+2]=cnt[2*x+2][v];
    lazy[2*x+1]=lazy[2*x+2]=v;
    lazy[x]=no_op;
  }

  void upd(int l, int r, int v, int x, int lx, int rx){
    push(x, lx, rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r){
      lazy[x]=v;
      good[x]=cnt[x][v];
      return;
    }
    int m=(lx+rx)/2;
    upd(l, r, v, 2*x+1, lx, m);
    upd(l, r, v, 2*x+2, m, rx);
    good[x]=good[2*x+1]+good[2*x+2];
  }

  void upd(int l, int r, int v){ upd(l, r, v, 0, 0, n); }
  bool query(){ return good[0]==n; }
};

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> a >> b >> c;
  map<char, char> mp={{'J', '0'}, {'O', '1'}, {'I', '2'}};
  for(int i=0; i<n; i++){
    a[i]=mp[a[i]];
    b[i]=mp[b[i]];
    c[i]=mp[c[i]];
  }

  vector<segtree> seg;
  vector<int> h(3);
  h[0]=h[1]=h[2]=1;
  for(int z=0; z<3; z++){
    h[z]=-1;
    string s="";
    for(int p=0; p<n; p++){
      int A=a[p]-'0';
      int B=b[p]-'0';
      int C=c[p]-'0';
      int d=(h[0]*A+h[1]*B+h[2]*C+9)%3;
      s+=static_cast<char>('0'+d);
    }
    segtree st(n, s);
    seg.push_back(st);
    h[z]=1;
  }

  h[0]=h[1]=h[2]=-1;
  for(int z=0; z<3; z++){
    h[z]=0;
    string s="";
    for(int p=0; p<n; p++){
      int A=a[p]-'0';
      int B=b[p]-'0';
      int C=c[p]-'0';
      int d=(h[0]*A+h[1]*B+h[2]*C+9)%3;
      s+=static_cast<char>('0'+d);
    }
    segtree st(n, s);
    seg.push_back(st);
    h[z]=-1;
  }

  h[0]=h[1]=h[2]=0;
  for(int z=0; z<3; z++){
    h[z]=1;
    string s="";
    for(int p=0; p<n; p++){
      int A=a[p]-'0';
      int B=b[p]-'0';
      int C=c[p]-'0';
      int d=(h[0]*A+h[1]*B+h[2]*C+9)%3;
      s+=static_cast<char>('0'+d);
    }
    segtree st(n, s);
    seg.push_back(st);
    h[z]=0;
  }

  auto upd=[&](int l, int r, int v){
    for(int i=0; i<9; i++){
      seg[i].upd(l, r, v);
    }
  };

  auto any=[&]()->bool{
    for(int i=0; i<9; i++){
      if(seg[i].query()) return 1;
    }
    return 0;
  };

  cin >> q >> t;
  for(int i=0; i<n; i++){
    upd(i, i+1, mp[t[i]]-'0');
  }
  cout << (any()?"Yes":"No") << "\n";
  while(q--){
    int l, r; char c; cin >> l >> r >> c;
    l--, r--;
    int v=mp[c]-'0';
    upd(l, r+1, v);
    cout << (any()?"Yes":"No") << "\n";
  }
}

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