| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 804635 |
2023-08-03T10:36:10 Z |
myst6 |
Crossing (JOI21_crossing) |
C++14 |
|
3602 ms |
32424 KB |
#include <bits/stdc++.h>
using namespace std;
struct intervals {
set<pair<int,int>> LR;
intervals() {}
void _add(int l, int r) {
if (l > r) return;
else LR.insert({l, r});
}
void add(int l, int r) {
remove(l, r);
_add(l, r);
}
void remove(int l, int r) {
auto it = LR.lower_bound({l,0});
if (it != LR.begin()) {
--it;
int l2 = it->first;
int r2 = it->second;
LR.erase(it);
_add(l2,min(l-1,r2));
it = LR.lower_bound({l,0});
}
while (it != LR.end() && it->first <= r) {
int l2 = it->first;
int r2 = it->second;
LR.erase(it);
_add(max(r+1,l2),r2);
it = LR.lower_bound({l,0});
}
}
void print() {
for (pair<int,int> seg : LR) {
cout << "[" << seg.first << "," << seg.second << "] U ";
}
cout << "[] \n";
}
bool empty() {
return LR.empty();
}
};
struct segtree {
vector<char> orig;
vector<char> upd;
intervals wrong;
segtree(string s) {
int sz = (int)s.size();
orig.resize(sz*4,0);
upd.resize(sz*4,0);
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 check(int x, int xl, int xr) {
if (upd[x] != orig[x]) {
wrong.add(xl, xr);
} else {
wrong.remove(xl, xr);
}
}
void pushdown(int x, int xl, int xr) {
if (xl == xr) return;
if (upd[x] == '0') return;
wrong.remove(xl, xr);
int xm = (xl + xr) >> 1;
if (lc(x) < upd.size()) {
upd[lc(x)] = upd[x];
check(lc(x), xl, xm);
}
if (rc(x) < upd.size()) {
upd[rc(x)] = upd[x];
check(rc(x), xm+1, xr);
}
upd[x] = '0';
}
void update(int l, int r, int x, int xl, int xr, char c) {
if (l > r) return;
cout << l << "," << r << "," << x << "," << xl << "," << xr << endl;
assert(x != 0);
pushdown(x, xl, xr);
if (l == xl && r == xr) {
upd[x] = c;
check(x, xl, xr);
} else {
int xm = (xl + xr) >> 1;
update(l, min(xm,r), lc(x), xl, xm, c);
update(max(xm+1,l), r, rc(x), xm+1, xr, c);
}
}
};
int main() {
int n;
cin >> n;
string a, b, c;
cin >> a >> b >> c;
if (a == b && b == c) {
segtree tree(a);
int q;
cin >> q;
string t;
cin >> t;
for (int i=0; i<(int)t.size(); i++) {
tree.update(i,i,1,0,n-1,t[i]);
}
cout << ( tree.wrong.empty() ? "YES" : "NO" ) << "\n";
// tree.wrong.print();
for (int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
l--, r--;
char c;
cin >> c;
tree.update(l,r,1,0,n-1,c);
cout << ( tree.wrong.empty() ? "YES" : "NO" ) << "\n";
// tree.wrong.print();
}
} else { // F
}
return 0;
}
Compilation message
Main.cpp: In member function 'void segtree::pushdown(int, int, int)':
Main.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if (lc(x) < upd.size()) {
| ~~~~~~^~~~~~~~~~~~
Main.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (rc(x) < upd.size()) {
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3602 ms |
32424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3602 ms |
32424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3602 ms |
32424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3602 ms |
32424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
