Submission #493564

#	Time	Username	Problem	Language	Result	Execution time	Memory
493564		600Mihnea	Crossing (JOI21_crossing)	C++17	100 / 100	2696 ms	107824 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

class Node {
public:
  bool stequal = false;
  bool jequal = false;
  bool oequal = false;
  bool iequal = false;
};

class IsEqual {
private:
  vector<string> s;
  string t;
  int n;
  vector<vector<Node>> tree;
  vector<vector<char>> lazy;

  void build(int v, int tl, int tr) {
    if (tl == tr) {
      for (int j = 0; j < 9; j++) {
        tree[v][j].stequal = (s[j][tl] == t[tl]);
        tree[v][j].jequal = (s[j][tl] == 'J');
        tree[v][j].oequal = (s[j][tl] == 'O');
        tree[v][j].iequal = (s[j][tl] == 'I');
      }

    } else {
      int tm = (tl + tr) / 2;
      build(2 * v, tl, tm);
      build(2 * v + 1, tm + 1, tr);
      for (int j = 0; j < 9; j++) {
        tree[v][j].stequal = tree[2 * v][j].stequal & tree[2 * v + 1][j].stequal;
        tree[v][j].jequal = tree[2 * v][j].jequal & tree[2 * v + 1][j].jequal;
        tree[v][j].oequal = tree[2 * v][j].oequal & tree[2 * v + 1][j].oequal;
        tree[v][j].iequal = tree[2 * v][j].iequal & tree[2 * v + 1][j].iequal;
      }
    }
  }

  void modify(int v, int tl, int tr, int l, int r, char ch) {
    for (int j = 0; j < 9; j++) {

      if (lazy[v][j] != 'X') {
        if (lazy[v][j] == 'J') {
          tree[v][j].stequal = tree[v][j].jequal;
        } else {
          if (lazy[v][j] == 'O') {
            tree[v][j].stequal = tree[v][j].oequal;
          } else {
            tree[v][j].stequal = tree[v][j].iequal;
          }
        }
        if (tl < tr) {
          lazy[2 * v][j] = lazy[2 * v + 1][j] = lazy[v][j];
        }
        lazy[v][j] = 'X';
      }
    }
    if (tr < l || r < tl) {
      return;
    }
    if (l <= tl && tr <= r) {
      for (int j = 0; j < 9; j++) {
        lazy[v][j] = ch;
        if (lazy[v][j] == 'J') {
          tree[v][j].stequal = tree[v][j].jequal;
        } else {
          if (lazy[v][j] == 'O') {
            tree[v][j].stequal = tree[v][j].oequal;
          } else {
            tree[v][j].stequal = tree[v][j].iequal;
          }
        }
        if (tl < tr) {
          lazy[2 * v][j] = lazy[2 * v + 1][j] = lazy[v][j];
        }
        lazy[v][j] = 'X';
      }
    } else {
      int tm = (tl + tr) / 2;
      modify(2 * v, tl, tm, l, r, ch);
      modify(2 * v + 1, tm + 1, tr, l, r, ch);
      for (int j = 0; j < 9; j++) {
        tree[v][j].stequal = tree[2 * v][j].stequal & tree[2 * v + 1][j].stequal;
      }
    }
  }

public:

  IsEqual(vector<string> s, string t) : s(s), t(t), n((int) t.size()), tree(4 * ((int) t.size() + 7), vector<Node> (9)), lazy(4 * ((int) t.size() + 7), vector<char> (9, 'X')) {
    build(1, 0, n - 1);
  }

  void modify(int l, int r, char ch) {
    l--;
    r--;
    modify(1, 0, n - 1, l, r, ch);
  }

  bool isEqual() {
    bool ok = false;
    for (int j = 0; j < 9; j++) {
      ok |= tree[1][j].stequal;
    }
    return ok;
  }
};

string operator + (string s, string t) {
  for (int i = 0; i < (int) s.size(); i++) {
    if (s[i] != t[i]) {
      int x = 'J' + 'O' + 'I' - s[i] - t[i];
      s[i] = x;
    }
  }
  return s;
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

 // freopen ("TonyStark", "r", stdin);

  int n, q;
  string a, b, c, t;
  cin >> n >> a >> b >> c >> q >> t;
  vector<string> strs;
  strs.push_back(a);
  strs.push_back(b);
  strs.push_back(c);
  strs.push_back(a + b);
  strs.push_back(b + c);
  strs.push_back(c + a);
  strs.push_back(a + (b + c));
  strs.push_back(b + (c + a));
  strs.push_back(c + (a + b));

  IsEqual all(strs, t);


  function <string()> solve = [&] () {
    if (all.isEqual()) {
      return "Yes";
    } else {
      return "No";
    }
  };

  cout << solve() << "\n";

  while (q--) {
    int l, r;
    string ch;
    cin >> l >> r >> ch;
    all.modify(l, r, ch[0]);
    cout << solve() << "\n";
  }
}

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