QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
}
详细
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%