제출 #870015

#제출 시각아이디문제언어결과실행 시간메모리
870015NeroZeinCrossing (JOI21_crossing)C++17
100 / 100
1913 ms119588 KiB
    #include "bits/stdc++.h"
    using namespace std;
     
    #ifdef Nero
    #include "Deb.h"
    #else
    #define deb(...)
    #endif
     
    const int V = 30; 
    const int N = 2e5 + 5; 
     
    int cnt = 3; 
    int a[V][N]; 
    int lazy[N * 2]; 
    int ch[V][N * 2], seg[V][N * 2];
     
    void build(int ver, int nd, int l, int r) {
      if (l == r) {
        ch[ver][nd] = a[ver][l];
        seg[ver][nd] = ch[ver][nd] == ch[cnt][nd]; 
        return;
      }
      int mid = (l + r) >> 1;
      int rs = nd + ((mid - l + 1) << 1);
      build(ver, nd + 1, l, mid);
      build(ver, rs, mid + 1, r);
      seg[ver][nd] = (seg[ver][nd + 1] & seg[ver][rs]); 
      ch[ver][nd] = (ch[ver][nd + 1] == ch[ver][rs] ? ch[ver][rs] : -1); 
    }
     
    void push(int nd, int l, int r) {
      if (!lazy[nd]) return;
      ch[cnt][nd] = lazy[nd];
      for (int i = cnt; i >= 0; --i) {
        seg[i][nd] = ch[i][nd] == ch[cnt][nd]; 
      }
      if (l != r) {
        int mid = (l + r) >> 1;
        int rs = nd + ((mid - l + 1) << 1);
        lazy[nd + 1] = lazy[nd];
        lazy[rs] = lazy[nd]; 
      }
      lazy[nd] = 0;
    }
     
    void upd(int nd, int l, int r, int s, int e, int v) {
      push(nd, l, r); 
      if (l >= s && r <= e) {
        lazy[nd] = v; 
        push(nd, l, r);
        return;
      }
      int mid = (l + r) >> 1;
      int rs = nd + ((mid - l + 1) << 1);
      if (mid >= e) {
        push(rs, mid + 1, r); 
        upd(nd + 1, l, mid, s, e, v);
      } else {
        if (mid < s) {
          push(nd + 1, l, mid); 
          upd(rs, mid + 1, r, s, e, v);      
        } else {
          upd(nd + 1, l, mid, s, e, v);      
          upd(rs, mid + 1, r, s, e, v);      
        }
      }
      for (int i = 0; i <= cnt; ++i) {
        seg[i][nd] = seg[i][nd + 1] & seg[i][rs]; 
        ch[i][nd] = ch[i][nd + 1] == ch[i][rs] ? ch[i][rs] : -1;     
      } 
    }
     
    int main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      int n;
      cin >> n; 
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < n; ++j) {
          char c;
          cin >> c;
          a[i][j] = (c == 'J' ? 1 : c == 'O' ? 2 : 3); 
        }
      }
      auto merge = [&](int x, int y, int z) {
        for (int i = 0; i < n; ++i) {
          a[z][i] = a[x][i] == a[y][i] ? a[y][i] : a[y][i] ^ a[x][i];
        }
      }; 
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
          for (int k = 0; k < 3; ++k) {
            if (i == j && j == k) {
              continue;
            }
            merge(i, j, cnt);
            merge(cnt, k, cnt); 
            cnt++; 
          }
        }
      }
      int q;
      cin >> q;
      for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        a[cnt][i] = (c == 'J' ? 1 : c == 'O' ? 2 : 3); 
      }
      for (int i = cnt; i >= 0; --i) {
        build(i, 0, 0, n - 1); 
      }
      bool ans = false;
      for (int i = 0; i < cnt; ++i) {
        ans |= seg[i][0] == 1; 
      }
      cout << (ans ? "Yes" : "No") << '\n'; 
      while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        char c;
        cin >> c;
        int x = (c == 'J' ? 1 : c == 'O' ? 2 : 3); 
        upd(0, 0, n - 1, l, r, x); 
        ans = false;
        for (int i = 0; i < cnt; ++i) {
          ans |= seg[i][0] == 1; 
        }
        cout << (ans ? "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...