Submission #1037105

#TimeUsernameProblemLanguageResultExecution timeMemory
1037105juicyCrossing (JOI21_crossing)C++17
0 / 100
47 ms8540 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 2e5 + 5, base = 4; int n, q; long long pw[N], pf[N], sum[N], s[4 * N]; int lz[4 * N]; map<long long, bool> mp; string S; int conv(char c) { return c == 'J' ? 1 : (c == 'O' ? 2 : 3); } void bld(int id = 1, int l = 1, int r = n) { sum[id] = pf[r - l]; if (l == r) { s[id] = conv(S[l - 1]); return; } int md = (l + r) / 2; bld(id * 2, l, md); bld(id * 2 + 1, md + 1, r); s[id] = s[id * 2] * pw[r - md] + s[id * 2 + 1]; } void app(int id, int x) { s[id] = sum[id] * x; lz[id] = x; } void psh(int id) { if (lz[id]) { app(id * 2, lz[id]); app(id * 2 + 1, lz[id]); lz[id] = 0; } } void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) { if (u <= l && r <= v) { app(id, x); return; } psh(id); int md = (l + r) / 2; if (u <= md) { upd(u, v, x, id * 2, l, md); } if (md < v) { upd(u, v, x, id * 2 + 1, md + 1, r); } s[id] = s[id * 2] * pw[r - md] + s[id * 2 + 1]; } string cross(const string &a, const string &b) { string res; for (int i = 0; i < n; ++i) { if (a[i] == b[i]) { res += a[i]; } else { for (auto c : {'J', 'O', 'I'}) { if (c != a[i] && c != b[i]) { res += c; } } } } return res; } long long get(const string &s) { long long h = 0; for (char c : s) { h = h * base + conv(c); } return h; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; vector<string> st; for (int i = 0; i < 3; ++i) { string s; cin >> s; st.push_back(s); mp[get(s)] = 1; } for (int i = 0; i < 3; ++i) { for (int j = i + 1; j < 3; ++j) { auto mix = cross(st[i], st[j]); auto h = get(mix); if (!mp.count(h)) { mp[h] = 1; st.push_back(mix); } } } bool flg = 1; while (flg) { flg = 0; for (int i = 0; i + 1 < st.size(); ++i) { auto mix = cross(st[i], st.back()); auto h = get(mix); if (!mp.count(h)) { st.push_back(mix); mp[h] = 1; flg = 1; break; } } } pw[0] = pf[0] = 1; for (int i = 1; i <= n; ++i) { pw[i] = pw[i - 1] * base; pf[i] = pf[i - 1] + pw[i]; } cin >> q >> S; bld(); auto qry = [&]() { cout << (mp.count(s[1]) ? "Yes" : "No") << "\n"; }; qry(); while (q--) { int l, r; char c; cin >> l >> r >> c; upd(l, r, conv(c)); qry(); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i + 1 < st.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...