Submission #526625

#TimeUsernameProblemLanguageResultExecution timeMemory
526625jalsolCrossing (JOI21_crossing)C++11
49 / 100
211 ms14748 KiB
#include <bits/stdc++.h> using namespace std; #define Task "" struct __Init__ { __Init__() { cin.tie(nullptr)->sync_with_stdio(false); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } } } __init__; using ll = long long; #ifdef LOCAL #define debug(x) cerr << "[" #x " = " << x << "]\n"; #else #define debug(...) #endif // LOCAL #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define fi first #define se second #define For(i, l, r) for (int i = (l); i <= (r); ++i) #define Ford(i, r, l) for (int i = (r); i >= (l); --i) #define Rep(i, n) For (i, 0, (n) - 1) #define Repd(i, n) Ford (i, (n) - 1, 0) template<class C> int isz(const C& c) { return c.size(); } template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; } constexpr int eps = 1e-9; constexpr int inf = 1e9; constexpr ll linf = 1e18; // ============================================================================= constexpr int maxN = 2e5 + 5; constexpr int base = 5; struct mint { int v; static constexpr int mod = 1e9 + 123; mint() : v() {} mint(ll _v) : v(_v % mod) { v += mod * (v < 0); } mint& operator+=(const mint& o) { if ((v += o.v) >= mod) v -= mod; return *this; } mint& operator*=(const mint& o) { return *this = mint(1LL * v * o.v); } friend mint operator+(const mint& a, const mint& b) { return mint(a) += b; } friend mint operator*(const mint& a, const mint& b) { return mint(a) *= b; } bool operator==(const mint& o) const { return v == o.v; } }; int n, nq; string s[3]; string t; unordered_map<char, int> mp = {{'J', 1}, {'O', 2}, {'I', 3}}; mint pw[maxN]; mint consec[4][maxN]; namespace Tree { mint tree[maxN << 2]; int lazy[maxN << 2]; #define m ((l + r) / 2) void pull(int i, int l, int r) { tree[i] = tree[i << 1] * pw[r - m] + tree[i << 1 | 1]; } void push(int i, int l, int r) { if (lazy[i] == 0) return; tree[i] = consec[lazy[i]][r - l + 1]; if (l < r) { lazy[i << 1] = lazy[i]; lazy[i << 1 | 1] = lazy[i]; } lazy[i] = 0; } void build(int i, int l, int r) { if (l == r) { tree[i] = mp[t[l - 1]]; return; } build(i << 1, l, m); build(i << 1 | 1, m + 1, r); pull(i, l, r); } void update(int u, int v, int x, int i, int l, int r) { push(i, l, r); if (v < l || r < u) return; if (u <= l && r <= v) { lazy[i] = x; push(i, l, r); return; } update(u, v, x, i << 1, l, m); update(u, v, x, i << 1 | 1, m + 1, r); pull(i, l, r); } #undef m } // namespace Tree using namespace Tree; struct Sub2 { void solve() { cin >> nq >> t; build(1, 1, n); mint target = 0; For (i, 1, n) { target = target * base + mp[s[0][i - 1]]; } cout << (target == tree[1] ? "Yes" : "No") << '\n'; Rep (_, nq) { int l, r; char c; cin >> l >> r >> c; update(l, r, mp[c], 1, 1, n); cout << (target == tree[1] ? "Yes" : "No") << '\n'; } } }; struct Sub3 { set<string> st; vector<string> v {s[0], s[1], s[2]}; string combine(const string &a, const string& b) { string ret(n, ' '); Rep (i, n) { if (a[i] == b[i]) { ret[i] = a[i]; } else { ret[i] = ('J' + 'O' + 'I') - (a[i] + b[i]); } } return ret; } void solve() { st.insert(all(v)); Rep (i, isz(v)) { For (j, i + 1, isz(v) - 1) { string nxt = combine(v[i], v[j]); if (st.insert(nxt).se) { v.push_back(nxt); } } } cin >> nq >> t; cout << (st.count(t) ? "Yes" : "No") << '\n'; Rep (_, nq) { int l, r; char c; cin >> l >> r >> c; For (i, l, r) t[i - 1] = c; cout << (st.count(t) ? "Yes" : "No") << '\n'; } } }; signed main() { cin >> n; Rep (i, 3) cin >> s[i]; pw[0] = 1; For (i, 1, maxN - 1) pw[i] = pw[i - 1] * base; For (i, 1, maxN - 1) { For (c, 1, 3) { consec[c][i] = consec[c][i - 1] * base + c; } } #define SUB(x) \ Sub##x* sol = new Sub##x{}; \ sol->solve(); delete sol if (s[0] == s[1] && s[1] == s[2]) { SUB(2); } else if (n <= 100) { SUB(3); } } /* abc def 1 6 m = 3 m + 1 -> r: 6 - 3 = 3 */

Compilation message (stderr)

Main.cpp: In constructor '__Init__::__Init__()':
Main.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "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...