Submission #881572

#	Time	Username	Problem	Language	Result	Execution time	Memory
881572		nima_aryan	Crossing (JOI21_crossing)	C++17	100 / 100	350 ms	45528 KiB

Main

/**
 *    author:  NimaAryan
 *    created: 2023-12-01 12:26:57  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 M = 1E9 + 7;
constexpr i64 B = 28463;

vector<i64> powB{1};
vector<vector<i64>> hashC(3, {0});

void init() {
  while (powB.size() < 3E5) {
    powB.push_back(powB.back() * B % M);
  }
  for (int i = 0; i < 3; ++i) {
    while (hashC[i].size() < 3E5) {
      hashC[i].push_back((hashC[i].back() * B + i) % M);
    }
  }
}

struct Tag {
  int ch = -1;

  void apply(const Tag& v) {
    if (v.ch != -1) {
      ch = v.ch;
    }
  }
};
struct Info {
  int len = 0;
  i64 hash = 0;

  void apply(int l, int r, const Tag& v) {
    if (v.ch != -1) {
      len = r - l;
      hash = hashC[v.ch][len];
    }
  }
};
Info operator+(Info a, Info b) {
  Info res;
  res.len = a.len + b.len;
  res.hash = (a.hash * powB[b.len] % M + b.hash) % M;
  return res;
}

class SegmentTree {
 public:
  int n;
  vector<Info> info;
  vector<Tag> tag;

  SegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
    tag.assign(4 << __lg(n), Tag());
  }

  void pull(int p) {
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void apply(int p, int l, int r, const Tag& v) {
    info[p].apply(l, r, v);
    tag[p].apply(v);
  }
  void push(int p, int l, int r) {
    int m = (l + r) / 2;
    apply(2 * p, l, m, tag[p]);
    apply(2 * p + 1, m, r, tag[p]);
    tag[p] = Tag();
  }

  void range_apply(int p, int l, int r, int lx, int rx, const Tag& v) {
    if (l >= rx || r <= lx) {
      return;
    }
    if (l >= lx && r <= rx) {
      apply(p, l, r, v);
      return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    range_apply(2 * p, l, m, lx, rx, v);
    range_apply(2 * p + 1, m, r, lx, rx, v);
    pull(p);
  }
  void range_apply(int lx, int rx, const Tag& v) {
    range_apply(1, 0, n, lx, rx, v);
  }
};

int asc(char c) {
  return c == 'J' ? 0 : (c == 'O' ? 1 : 2);
}
vector<int> conv(string s) {
  vector<int> res;
  for (int i = 0; i < s.size(); ++i) {
    res.push_back(asc(s[i]));
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  init();

  int N;
  cin >> N;

  vector<vector<int>> S(3);
  for (int i = 0; i < 3; ++i) {
    string t;
    cin >> t;
    S[i] = conv(t);
  }

  set<vector<int>> a;
  for (int i = 0; i < 3; ++i) {
    a.insert(S[i]);
  }
  while (true) {
    auto new_a = a;
    for (auto s : a) {
      for (auto t : a) {
        if (s != t) {
          vector<int> u;
          for (int i = 0; i < N; ++i) {
            u.push_back((6 - (s[i] + t[i])) % 3);
          }
          if (!new_a.count(u)) {
            new_a.insert(u);
          }
        }
      }
    }
    if (a == new_a) {
      break;
    }
    a.swap(new_a);
  }

  set<i64> search;
  for (auto s : a) {
    i64 hash = 0;
    for (int i = 0; i < N; ++i) {
      hash = (hash * B + s[i]) % M;
    }
    search.insert(hash);
  }

  int Q;
  cin >> Q;

  string T;
  cin >> T;

  auto t = conv(T);

  SegmentTree seg(N);
  for (int i = 0; i < N; ++i) {
    seg.range_apply(i, i + 1, Tag{t[i]});
  }

  i64 hash = seg.info[1].hash;
  if (search.count(hash)) {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }

  while (Q--) {
    int L, R;
    cin >> L >> R;
    --L;
    char C;
    cin >> C;
    seg.range_apply(L, R, Tag{asc(C)});
    i64 hash = seg.info[1].hash;
    if (search.count(hash)) {
      cout << "Yes" << "\n";
    } else {
      cout << "No" << "\n";
    }
  }

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> conv(std::string)':
Main.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~

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