Submission #1348792

#TimeUsernameProblemLanguageResultExecution timeMemory
1348792ramzialoulouCrossing (JOI21_crossing)C++20
26 / 100
109 ms8104 KiB
#include <bits/stdc++.h>
 
using namespace std;

const int N = int(2e5) + 9;
string s, t;
int seg[4 * N], lzy[4 * N];
int cnt[4][N];

int id(char c) {
  if (c == 'J') {
    return 1;
  } else if (c == 'O') {
    return 2;
  } else {
    return 3;
  }
}

int count(int l, int r, int v) {
  return cnt[v][r + 1] - cnt[v][l];
}

void push(int nd, int l, int r) {
  if (!lzy[nd]) {
    return;
  }
  int mid = (l + r) >> 1;
  seg[nd * 2] = count(l, mid, lzy[nd]);
  seg[nd * 2 + 1] = count(mid + 1, r, lzy[nd]);
  lzy[nd * 2] = lzy[nd];
  lzy[nd * 2 + 1] = lzy[nd];
  lzy[nd] = 0;
}

void upd(int nd, int l, int r, int x, int y, int v) {
  if (l > y || r < x) {
    return;
  }
  if (x <= l && r <= y) {
    seg[nd] = count(l, r, v);
    lzy[nd] = v;
    return;
  }
  push(nd, l, r);
  int mid = (l + r) >> 1;
  upd(nd * 2, l, mid, x, y, v);
  upd(nd * 2 + 1, mid + 1, r, x, y, v);
  seg[nd] = seg[nd * 2] + seg[nd * 2 + 1];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  string s;
  cin >> s >> s >> s;
  for (int i = 1; i <= 3; i++) {
    for (int j = 0; j < n; j++) {
      cnt[i][j + 1] = cnt[i][j] + (id(s[j]) == i);
    }
  }
  int q;
  cin >> q;
  string t;
  cin >> t;
  for (int i = 0; i < n; i++) {
    upd(1, 0, n - 1, i, i, id(t[i]));
  }
  cout << (seg[1] == n ? "Yes" : "No") << '\n';
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    char c;
    cin >> c;
    upd(1, 0, n - 1, l, r, id(c));
    cout << (seg[1] == n ? "Yes" : "No") << '\n';
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...