Submission #600411

#	Time	Username	Problem	Language	Result	Execution time	Memory
600411		Plurm	Crossing (JOI21_crossing)	C++11	26 / 100	621 ms	12684 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 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;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> s >> s >> s;
  bp[0] = 1;
  for(int i = 1; i <= n; i++){
    bp[i] = 1ll * bp[i-1] * B % MOD;
  }
  prep();
  int q;
  cin >> q;
  cin >> t;
  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: 0 / 23
• Subtask 4: 0 / 51