Submission #1051894

#TimeUsernameProblemLanguageResultExecution timeMemory
1051894SacharlemagneCrossing (JOI21_crossing)C++17
0 / 100
38 ms4180 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9+7, BASE = 5, MXN = 2e5+5; ll Pow[MXN], Same[MXN]; ll getVal(char c) { if (c == 'J') return 1; if (c == 'O') return 2; return 3; } char cross(char a, char b) { if (a == b) return a; if (a != 'O' && b != 'O') return 'O'; if (a != 'J' && b != 'J') return 'J'; return 'I'; } string merge(string a, string b) { string c(a.size(), ' '); for (int i = 0; i<a.size(); ++i) { c[i] = cross(a[i], b[i]); } return c; } vector<ll> starter; struct Node { ll l,r, mid,sz, set, hash; Node *lp, *rp; void blaSet(ll val) { hash = val * Same[sz-1]; set = val; } void pull() { hash = lp->hash * Pow[lp->sz] + rp->hash; hash %= MOD; } void push() { if (set != -1) { lp->blaSet(set), rp->blaSet(set); set = -1; } } Node(ll l, ll r) : l(l), r(r), mid((l+r)/2), sz(r-l+1), set(-1) { if (l != r) { lp = new Node(l, mid), rp = new Node(mid+1,r); pull(); } else blaSet(starter[l]); } void update(int s, int e, ll val) { if (s > r || e < l) return; if (s <= l && e >= r) { blaSet(val); return; } if (s <= mid) lp->update(s,e,val); if (e > mid) rp->update(s,e,val); pull(); } }; void init() { Pow[0] = 1; Same[0] = 1; for (int i = 1; i<MXN; ++i) { Pow[i] = (Pow[i-1] * BASE) % MOD; Same[i] = (Same[i-1] * BASE + 1) % MOD; } } int main() { cin.tie(0)->sync_with_stdio(0); int n,q; cin >> n; init(); vector<string> start(3); set<string> s; for (string &S :start) { cin >> S; s.insert(S); } /*for (int i = 0; i<3; ++i) for (int j = i+1; j<3; ++j) s.insert(merge(start[i], start[j])); s.insert(merge(start[0], merge(start[2], start[1]))); s.insert(merge(start[1], merge(start[2], start[0]))); s.insert(merge(start[2], merge(start[1], start[0]))); */ ll tot = 0; for (int i = 0; i<n; ++i) tot = (tot*BASE + getVal(start[0][i])) % MOD; cin >> q; string seq; cin >> seq; cout << (s.count(seq) ? "Yes" : "No") << '\n'; starter.resize(n); for (int i = 0; i<n; ++i) starter[i] = getVal(seq[i]); Node *seg = new Node(0, n-1); while (q--) { int l,r; char c; cin >> l >> r >> c; ll ne = getVal(c); seg->update(l-1,r-1,ne); cout << (seg->hash == tot ? "Yes" : "No") << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i<a.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...