| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 804905 |
2023-08-03T11:52:41 Z |
myst6 |
Crossing (JOI21_crossing) |
C++14 |
|
358 ms |
1048576 KB |
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
struct segtree {
vector<char> orig;
vector<char> upd;
vector<bool> match;
segtree(string s) {
int sz = (int)s.size();
orig.resize(sz*4,0);
upd.resize(sz*4,0);
match.resize(sz*4,1);
build(s,1,0,sz-1);
}
int lc(int x) { return x << 1; }
int rc(int x) { return lc(x) | 1; }
void build(string &s, int x, int xl, int xr) {
if (xl == xr) orig[x] = upd[x] = s[xl];
else {
int xm = (xl + xr) >> 1;
build(s,lc(x),xl,xm);
build(s,rc(x),xm+1,xr);
if (orig[lc(x)] == orig[rc(x)]) {
orig[x] = upd[x] = orig[lc(x)];
}
}
}
void pushdown(int x) {
if (upd[x] == '0') return;
if (lc(x) < upd.size()) {
upd[lc(x)] = upd[x];
match[lc(x)] = upd[lc(x)] == orig[lc(x)];
}
if (rc(x) < upd.size()) {
upd[rc(x)] = upd[x];
match[rc(x)] = upd[rc(x)] == orig[rc(x)];
}
upd[x] = '0';
}
void update(int l, int r, int x, int xl, int xr, char c) {
if (l > r) return;
if (l == xl && r == xr) {
upd[x] = c;
match[x] = upd[x] == orig[x];
} else {
int xm = (xl + xr) >> 1;
pushdown(x);
update(l, min(xm,r), lc(x), xl, xm, c);
update(max(xm+1,l), r, rc(x), xm+1, xr, c);
pushdown(lc(x)); pushdown(rc(x));
match[x] = match[lc(x)] && match[rc(x)];
}
}
bool query() {
return match[1];
}
};
string cross(string a, string b) {
string out = a;
for (int i=0; i<(int)a.size(); i++) {
if (a[i] != b[i]) {
set<char> C = {'J', 'O', 'I'};
C.erase(a[i]);
C.erase(b[i]);
out[i] = *C.begin();
}
}
return out;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int n;
cin >> n;
string a, b, c;
cin >> a >> b >> c;
string d = cross(a, b);
string e = cross(b, c);
string f = cross(c, a);
string g = cross(d, e);
string h = cross(e, f);
string i = cross(f, d);
set<string> V = {a,b,c,d,e,f,g,h,i};
// cerr << V.size() << endl;
vector<segtree> trees;
for (const string &s : V) {
trees.push_back(segtree(s));
}
int q;
cin >> q;
string t;
cin >> t;
for (int i=0; i<(int)t.size(); i++) {
for (segtree &tree : trees) tree.update(i,i,1,0,n-1,t[i]);
}
auto output_ans = [&]() {
bool ans = false;
for (segtree &tree : trees) {
if (tree.query()) {
ans = true;
break;
}
}
cout << ( ans ? "Yes" : "No" ) << "\n";
};
output_ans();
for (int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
l--, r--;
char c;
cin >> c;
for (segtree &tree : trees) tree.update(l,r,1,0,n-1,c);
output_ans();
}
return 0;
}
Compilation message
Main.cpp: In member function 'void segtree::pushdown(int)':
Main.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if (lc(x) < upd.size()) {
| ~~~~~~^~~~~~~~~~~~
Main.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if (rc(x) < upd.size()) {
| ~~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
358 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
358 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
358 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
358 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
