Submission #513163

#	Time	Username	Problem	Language	Result	Execution time	Memory
513163		czhang2718	Crossing (JOI21_crossing)	C++17	0 / 100	137 ms	27204 KiB

Main

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

typedef vector<int> vi;

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

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

struct segtree{
  int n;
  string s;
  vector<vi> cnt;
  vector<int> lazy;
  vector<int> good;

  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;
    cnt.resize(4*n, vi(3));
    lazy.resize(4*n, no_op);
    good.resize(4*n); 
    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]];
  }
  // cout << a << " " << b << " " << c << '\n';

  vector<segtree> seg;
  map<string, bool> have;
  vector<string> vec;
  for(int i=-1; i<=1; i++){
    for(int j=-1; j<=1; j++){
      for(int k=-1; k<=1; k++){
        // if(!i && !j && !k) continue;
        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=(i*A+j*B+k*C+9)%3;
          s+=static_cast<char>('0'+d);
        }
        // cout << s << "\n";
        vec.push_back(s);
        have[s]=1;
        segtree st(n, s);
        seg.push_back(st);
      }
    }
  }

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

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