Submission #804648

#TimeUsernameProblemLanguageResultExecution timeMemory
804648myst6Crossing (JOI21_crossing)C++14
0 / 100
478 ms1048576 KiB
#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; 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() { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); 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 (stderr)

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()) {
      |             ~~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...