제출 #750996

#제출 시각아이디문제언어결과실행 시간메모리
750996sysiaCrossing (JOI21_crossing)C++17
100 / 100
424 ms100568 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; void add(int &a, int b){ a += b; if (a >= mod) a-=mod; } int add2(int a, int b){ a += b; if (a >= mod) a-=mod; return a; } void sub(int &a, int b){ a -= b; if (a < 0) a += mod; } int mul(int a, int b){ return (a*b)%mod; } T f(T a, T b){ return T{add2(a.first, b.first), add2(a.second, b.second)}; } mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); int p(int a, int b){ return a + rng()%(b-a+1); } set<vector<int>>now; vector<int>A, B, C; int change(char c){ if (c == 'J') return 0; else if (c == 'O') return 1; return 2; } int sub2(int a, int b){ sub(a, b); return a; } T fsub(T a, T b){ return {sub2(a.first, b.first), sub2(a.second, b.second)}; } void gen(string &s, vector<int>&a){ for (auto c: s){ a.emplace_back(change(c)); } } vector<int> merge(vector<int>&a, vector<int>&b){ vector<int>ret; for (int i = 0; i<(int)a.size(); i++){ ret.emplace_back((2*a[i] + 2*b[i])%3); } return ret; } struct Q{ int l, r, c; T h; Q(){} Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {} bool operator <(const Q&he) const { return l < he.l; } }; void rec(vector<int>s){ if (now.find(s) != now.end()) return; now.insert(s); for (auto t: {A, B, C}){ rec(merge(s, t)); } } void solve(){ int n; cin >> n; string a, b, c; cin >> a >> b >> c; gen(a, A); gen(b, B); gen(c, C); for (auto s: {A, B, C}) rec(s); assert((int)now.size() <= 9); vector<T>Hash; int b1 = p(1, mod-1), b2 = p(1, mod-1); for (auto vt: now){ T H = {0, 0}, p = {1, 1}; for (auto ch: vt){ H = f(H, {mul(ch, p.first), mul(ch, p.second)}); p = {mul(p.first, b1), mul(p.second, b2)}; } Hash.emplace_back(H); } int q; cin >> q >> a; A.clear(); gen(a, A); set<Q>blocks; int begin = 0; T sum = {0, 0}, all = {0, 0}, p = {1, 1}; for (int i = 0; i<n; i++){ if (i && A[i] != A[i-1]){ blocks.insert({begin, i-1, sum, A[i-1]}); begin = i; all = f(all, sum); sum = {0, 0}; } sum = f(sum, {mul(A[i], p.first), mul(A[i], p.second)}); p = {mul(p.first, b1), mul(p.second, b2)}; } blocks.insert({begin, n-1, sum, A.back()}); all = f(all, sum); // for (auto [l, r, h, c]: blocks){ // debug(l, r, h, c); // } auto answer = [&](){ for (auto x: Hash){ if (x == all){ cout << "Yes\n"; return; } } cout << "No\n"; }; debug(all); answer(); vector<int>power1(n+1), power2(n+1); vector<int>pref1(n+1), pref2(n+1); power1[0] = power2[0] = 1; pref1[0] = pref2[0] = 1; for (int i = 1; i<=n; i++){ power1[i] = mul(power1[i-1], b1); power2[i] = mul(power2[i-1], b2); pref1[i] = add2(pref1[i-1], power1[i]); pref2[i] = add2(pref2[i-1], power2[i]); } auto get_sum = [&](int l, int r, int v) { if (r < l) return T{0ll, 0ll}; return T{mul(power1[l], mul(v, pref1[r-l])), mul(power2[l], mul(v, pref2[r-l]))}; }; vector<int>fix; while (q--){ int l, r; char d; cin >> l >> r >> d; --l;--r; debug(l, r, d); int what = change(d); auto wrr = prev(blocks.upper_bound({l, -oo, {-oo, -oo}, -oo})); fix.clear(); pair<Q, Q> tmp; tmp.first.l = -1; tmp.second.l = -1; for (auto it = wrr; it != blocks.end() && it->l <= r; it++){ auto [ll, rr, val, hh] = *it; fix.emplace_back(ll); // debug(ll, rr, val, hh); if (ll >= l && rr <= r){ all = fsub(all, hh); } else { //at most two such intervals bool sub = 0; if (ll < l){ tmp.first = {ll, l-1, get_sum(ll, l-1, val), val}; all = fsub(all, get_sum(l, min(rr, r), val)); sub = 1; } if (rr > r){ tmp.second = Q{r+1, rr, get_sum(r+1, rr, val), val}; if (!sub){ all = fsub(all, get_sum(max(ll, l), r, val)); } } } } debug(all); for (auto x: fix){ blocks.erase(blocks.lower_bound({x, -oo, {-oo, -oo}, -oo})); } blocks.insert({l, r, get_sum(l, r, what), what}); all = f(all, get_sum(l, r, what)); if (tmp.first.l != -1) blocks.insert(tmp.first); if (tmp.second.l != -1) blocks.insert(tmp.second); // for (auto [l, r, val, hh]: blocks){ // debug(l, r, val, hh); // } debug(all); answer(); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In constructor 'Q::Q(long long int, long long int, T, long long int)':
Main.cpp:95:7: warning: 'Q::h' will be initialized after [-Wreorder]
   95 |     T h;
      |       ^
Main.cpp:94:15: warning:   'long long int Q::c' [-Wreorder]
   94 |     int l, r, c;
      |               ^
Main.cpp:97:5: warning:   when initialized here [-Wreorder]
   97 |     Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...