Submission #493563

#	Time	Username	Problem	Language	Result	Execution time	Memory
493563		600Mihnea	Crossing (JOI21_crossing)	C++17	100 / 100	2088 ms	41644 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:
  string s;
  string t;
  int n;
  vector<Node> tree;
  vector<char> lazy;

  void build(int v, int tl, int tr) {
    if (tl == tr) {
      tree[v].stequal = (s[tl] == t[tl]);
      tree[v].jequal = (s[tl] == 'J');
      tree[v].oequal = (s[tl] == 'O');
      tree[v].iequal = (s[tl] == 'I');

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

  void modify(int v, int tl, int tr, int l, int r, char ch) {
    if (lazy[v] != 'X') { 
      if (lazy[v] == 'J') {
        tree[v].stequal = tree[v].jequal;
      } else {
        if (lazy[v] == 'O') {
          tree[v].stequal = tree[v].oequal;
        } else {
          tree[v].stequal = tree[v].iequal;
        }
      }
      if (tl < tr) {
        lazy[2 * v] = lazy[2 * v + 1] = lazy[v];
      }
      lazy[v] = 'X';
    }
    if (tr < l || r < tl) {
      return;
    }
    if (l <= tl && tr <= r) {
      lazy[v] = ch;
      if (lazy[v] == 'J') {
        tree[v].stequal = tree[v].jequal;
      } else {
        if (lazy[v] == 'O') {
          tree[v].stequal = tree[v].oequal;
        } else {
          tree[v].stequal = tree[v].iequal;
        }
      }
      if (tl < tr) {
        lazy[2 * v] = lazy[2 * v + 1] = lazy[v];
      }
      lazy[v] = '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);
      tree[v].stequal = tree[2 * v].stequal & tree[2 * v + 1].stequal;
    }
  }

public:

  IsEqual(string s, string t) : s(s), t(t), n((int) s.size()), tree(4 * ((int) s.size() + 7)), lazy(4 * ((int) s.size()), '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() {
    return tree[1].stequal;
  }
};

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);

  int n, q;
  string a, b, c, t;
  vector<IsEqual> all;
  cin >> n >> a >> b >> c >> q >> t;

  all.push_back({a, t});
  all.push_back({b, t});
  all.push_back({c, t});
  all.push_back({a + b, t});
  all.push_back({b + c, t});
  all.push_back({c + a, t});
  all.push_back({a + (b + c), t});
  all.push_back({b + (c + a), t});
  all.push_back({c + (a + b), t});


  function <string()> solve = [&] () {
    bool ok = false;
    for (auto &x : all) {
      ok |= x.isEqual();
    }
    if (ok) {
      return "Yes";
    } else {
      return "No";
    }
  };

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

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

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