제출 #1349376

#제출 시각아이디문제언어결과실행 시간메모리
1349376ramzialoulouCrossing (JOI21_crossing)C++20
100 / 100
4230 ms202616 KiB
#include <bits/stdc++.h>
 
using namespace std;

const int N = int(2e5) + 9;
const int M = 30;
int n;
int seg[M][4 * N], lzy[M][4 * N];
int cnt[M][4][N];

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

char idd(int v) {
  if (v == 1) {
    return 'J';
  } else if (v == 2) {
    return 'O';
  } else {
    return 'I';
  }
}

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

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

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

string merge(string a, string b) {
  string res = "";
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) {
      res += a[i];
    } else {
      res += idd(6 - id(a[i]) - id(b[i]));
    }
  }
  return res;
}

bool check() {
  for (int i = 0; i < M; i++) {
    if (seg[i][1] == n) {
      return true;
    }
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  vector<string> s(3);
  cin >> s[0] >> s[1] >> s[2];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        s.push_back(merge(merge(s[i], s[j]), s[k]));
      }
    }
  }
  for (int i = 0; i < M; i++) {
    for (int j = 1; j <= 3; j++) {
      for (int k = 0; k < n; k++) {
        cnt[i][j][k + 1] = cnt[i][j][k] + (id(s[i][k]) == j);
      }
    }
  }
  int q;
  cin >> q;
  string t;
  cin >> t;
  for (int j = 0; j < M; j++) {
    for (int i = 0; i < n; i++) {
      upd(1, 0, n - 1, i, i, id(t[i]), j);
    }
  }
  cout << (check() ? "Yes" : "No") << '\n';
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    char c;
    cin >> c;
    for (int i = 0; i < M; i++) {
      upd(1, 0, n - 1, l, r, id(c), i);
    }
    cout << (check() ? "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...