| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 885061 |
2023-12-09T00:30:45 Z |
Keys |
Crossing (JOI21_crossing) |
C++17 |
|
60 ms |
7540 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
7540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
7540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
7540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
7540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
