QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279809 | #1131. Crossing | willy108 | 0 | 50ms | 9216kb | C++20 | 2.6kb | 2023-12-09 09:51:32 | 2023-12-09 09:51:33 |
Judging History
answer
#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 = 9970003, mod = 1e9 + 7, N = 2e5 + 5;
int n, q, p[N], psum[N], st[N * 4], rset[N * 4];
string a[3], t;
set<int> se;
string joi = "JOI";
int hash_c(char c) {
if (c == 'J') return 0;
else if (c == 'O') return 1;
else return 2;
}
int hash_s(string s) {
int ret = 0;
for (int i = 0; i < int(s.size()); i++) (ret += p[i] * hash_c(s[i]) % mod) %= 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) % 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[2*v] = rset[v] * psum[r - m] % mod;
st[2*v+1] = rset[v] * psum[m - 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;
st[v] = rset[v] * psum[r - l + 1] % mod;
//push(v, l, r);
return;
}
push(v, l, r);
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 < int(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]))%3];
}
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[2], a[0]});
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;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 45ms
memory: 8856kb
input:
80 JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ 185606 IIJJOJIOJOIJIJJJJIOOJIIIIIIJIOIIOJOIJOIJOIJOJOI...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 185607 lines
Test #2:
score: 0
Accepted
time: 50ms
memory: 9176kb
input:
100 OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJJJOIOI OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJJJOIOI OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJ...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 200001 lines
Test #3:
score: 0
Accepted
time: 48ms
memory: 8804kb
input:
100 OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJIOJJOO OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJIOJJOO OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJ...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 200001 lines
Test #4:
score: -3
Wrong Answer
time: 37ms
memory: 9216kb
input:
97 OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII 194...
output:
Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No...
result:
wrong answer 46th lines differ - expected: 'Yes', found: 'No'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%