Submission #885061

#TimeUsernameProblemLanguageResultExecution timeMemory
885061KeysCrossing (JOI21_crossing)C++17
0 / 100
60 ms7540 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t #define endl '\n' #define dbg(x) cerr << #x << " = " << x << endl; typedef vector<int> vi; typedef vector<string> vs; const int base = 14347, mod = 1e9 + 7, N = 2e5 + 5; int n, q, p[N], psum[N], st[N * 4], rset[N * 4]; string a[3], t; map<char, int> m; set<int> se; string joi = "#JOI"; int hash_c(char c) { if (c == 'J') return 1; else if (c == 'O') return 2; else return 3; } int hash_s(string s) { int ret = 0; for (int i = 0; i < s.size(); i++) (ret += p[i] * hash_c(s[i])) %= mod; return ret; } void pull(int v, int l, int r) { int m = (l + r) / 2; st[v] = (st[2 * v] + st[2 * v + 1] * p[m - l + 1]) % mod; } void push(int v, int l, int r) { if (rset[v] == 0) return; int m = (l + r) / 2; rset[2 * v + 1] = rset[2 * v] = rset[v]; st[v] = rset[v] * psum[r - l + 1] % mod; rset[v] = 0; } void build(int v = 1, int l = 0, int r = n - 1) { if (l == r) { st[v] = hash_c(t[l]); } else { int m = (l + r) / 2; build(v * 2, l, m); build(v * 2 + 1, m + 1, r); pull(v, l, r); } } void upd(int ql, int qr, int x, int v = 1, int l = 0, int r = n - 1) { push(v, l, r); if (qr < l or ql > r) return; if (l >= ql and r <= qr) { rset[v] = x; push(v, l, r); return; } int m = (l + r) / 2; upd(ql, qr, x, v * 2, l, m); upd(ql, qr, x, v * 2 + 1, m + 1, r); pull(v, l, r); } void comb(vs a) { string s = a[0]; for (int i = 1; i < a.size(); i++) { string ns = ""; for (int j = 0; j < n; j++) { if (s[j] == a[i][j]) ns += s[j]; else ns += joi[6 - hash_c(s[j]) - hash_c(a[i][j])]; } s = ns; } se.insert(hash_s(s)); } signed main() { ios::sync_with_stdio(0); cin.tie(0); p[0] = 1; for (int i = 1; i < N; i++) p[i] = p[i - 1] * base % mod; for (int i = 1; i < N; i++) psum[i] = (psum[i - 1] + p[i - 1]) % mod; cin >> n >> a[0] >> a[1] >> a[2] >> q >> t; build(); comb({a[0]}); comb({a[1]}); comb({a[2]}); comb({a[0], a[1]}); comb({a[0], a[2]}); comb({a[1], a[2]}); comb({a[0], a[1], a[2]}); comb({a[0], a[2], a[1]}); comb({a[1], a[0], a[2]}); comb({a[1], a[2], a[0]}); comb({a[2], a[0], a[1]}); comb({a[2], a[1], a[0]}); cout << st[1] << endl; if (se.count(st[1])) cout << "YES" << endl; else cout << "NO" << endl; while (q--) { int l, r; char c; cin >> l >> r >> c; int o = hash_c(c); l--; r--; upd(l, r, o); if (se.count(st[1])) cout << "YES" << endl; else cout << "NO" << endl; } }

Compilation message (stderr)

Main.cpp: In function 'int64_t hash_s(std::string)':
Main.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < s.size(); i++) (ret += p[i] * hash_c(s[i])) %= mod;
      |                   ~~^~~~~~~~~~
Main.cpp: In function 'void push(int64_t, int64_t, int64_t)':
Main.cpp:38:7: warning: unused variable 'm' [-Wunused-variable]
   38 |   int m = (l + r) / 2;
      |       ^
Main.cpp: In function 'void comb(vs)':
Main.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int i = 1; 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...