Submission #600414

#	Time	Username	Problem	Language	Result	Execution time	Memory
600414		Plurm	Crossing (JOI21_crossing)	C++11	49 / 100	588 ms	12828 KiB

Main

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

const int MOD = 1e9+7;
const int B = 53;
const int invB = 788461544;
int bp[1 << 18];

string sa, sb, sc;
string s, t;

int templ;
void prep(){
  for(char c : s){
    templ = 1ll * templ * B % MOD;
    templ += c;
    templ %= MOD;
  }
}

int seg[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
char lazy[1 << 19];

void build(int c, int l, int r){
  lb[c] = l;
  rb[c] = r;
  if(l == r){
    seg[c] = t[l];
    return;
  }
  int k = (l + r)/2;
  build(2*c, l, k);
  build(2*c+1, k+1, r);
  seg[c] = (1ll * seg[2*c] * bp[r-k] % MOD + seg[2*c+1] % MOD) % MOD;
}

void prop(int c){
  if(lazy[c]){
    seg[c] = 1ll * lazy[c] * ((bp[rb[c] - lb[c] + 1] + MOD - 1) % MOD) % MOD * invB % MOD;
    if(lb[c] != rb[c]){
      lazy[2*c] = lazy[c];
      lazy[2*c+1] = lazy[c];
    }
    lazy[c] = '\0';
  }
}

void update(int c, int l, int r, char x){
  if(lb[c] == l && rb[c] == r) lazy[c] = x;
  prop(c);
  if(lb[c] == l && rb[c] == r) return;
  int k = (lb[c] + rb[c]) /2;
  if(l <= k && k < r){
    update(2*c, l, k, x);
    update(2*c+1, k+1, r, x);
  }else if(r <= k){
    update(2*c, l, r, x);
    prop(2*c+1);
  }else{
    prop(2*c);
    update(2*c+1, l, r, x);
  }
  seg[c] = (1ll * seg[2*c] * bp[rb[c]-k] % MOD + seg[2*c+1] % MOD) % MOD;
}

bool check(){
  prop(1);
  return seg[1] == templ;
}

string cross(string x, string y){
  if(x.empty()) return y;
  else if(y.empty()) return x;
  int n = x.size();
  string ret;
  for(int i = 0; i < n; i++){
    if(x[i] == y[i]) ret.push_back(x[i]);
    else ret.push_back(x[i] ^ y[i] ^ 'J' ^ 'O' ^ 'I');
  }
  return ret;
}

set<string> rec(int left, string cur = ""){
  if(left == 0) return {cur};
  set<string> s = {cur}, t;
  t = rec(left-1, cross(cur, sa));
  s.insert(t.begin(), t.end());
  t = rec(left-1, cross(cur, sb));
  s.insert(t.begin(), t.end());
  t = rec(left-1, cross(cur, sc));
  s.insert(t.begin(), t.end());
  return s;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> sa >> sb >> sc;
  int q;
  cin >> q;
  cin >> t;
  if(n <= 100){
    set<string> pool = rec(4);
    cout << (pool.count(t) ? "Yes" : "No") << endl;
    while(q--){
      int l, r;
      char c;
      cin >> l >> r >> c;
      for(int i = l; i <= r; i++){
        t[i-1] = c;
      }
      cout << (pool.count(t) ? "Yes" : "No") << endl;
    }
  }else{
    s = sa;
    bp[0] = 1;
    for(int i = 1; i <= n; i++){
      bp[i] = 1ll * bp[i-1] * B % MOD;
    }
    prep();
    build(1, 0, n-1);
    cout << (check() ? "Yes" : "No") << endl;
    while(q--){
      int l, r;
      char c;
      cin >> l >> r >> c;
      update(1, l-1, r-1, c);
      cout << (check() ? "Yes" : "No") << endl;
    }
  }
  
  return 0;
}

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