oj.uz

답안 #493561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493561 2021-12-12T06:19:25 Z 600Mihnea Crossing (JOI21_crossing) C++17
0 / 100
 335 ms 1000 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

/// Delete all asserts for extra Boost

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') { /// push
      assert(lazy[v] == 'J' || lazy[v] == 'O' || lazy[v] == 'I');
      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;
      assert(lazy[v] == 'J' || lazy[v] == 'O' || lazy[v] == 'I');
      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') {
    assert((int) s.size() == (int) t.size());
    build(1, 0, n - 1);
  }

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

  bool isEqual() {
    return tree[1].stequal;
  }
};

string operator + (string s, string t) {
  assert((int) s.size() == (int) t.size());
  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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 335 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 335 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 335 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 335 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -