# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
861405 | 2023-10-16T05:53:19 Z | vjudge1 | Crossing (JOI21_crossing) | C++17 | 95 ms | 17492 KB |
#include<bits/stdc++.h> using namespace std; #define int long long #define ll long long #define pii pair<int,int> #define F first #define S second #define endl '\n' #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() const int mod = 1e9 + 7, base = 13; const int N = 1e6 + 15; const ll inf = 1e18; vector<int> s[3]; int T[N]; char str[N]; int n, Q; struct Sgt{ #define ls (idx<<1) #define rs (idx<<1|1) static const int off = (1<<18); struct data{ int pws, val, tag; } t[N<<2]; void pull(int idx){ t[idx].pws = t[ls].pws + t[rs].pws; t[idx].val = t[ls].val + t[rs].val; return; } void push(int idx){ if (~t[idx].tag){ t[idx].val = t[idx].pws * t[idx].tag % mod; if (idx < off) t[ls].tag = t[rs].tag = t[idx].tag; t[idx].tag = ~0; } return; } void build(){ for (int idx=off, p=1;idx<off*2;idx++, p=1ll*p*base%mod){ t[idx].pws = p; t[idx].val = p*T[idx-off]; t[idx].tag = ~0; } for (int idx=off-1;idx>=1;idx--){ t[idx].pws = t[ls].pws+t[rs].pws; t[idx].val = t[ls].val+t[rs].val; t[idx].tag = ~0; } } void update(int l, int r, int val, int idx=1, int lo=0, int hi=off){ push(idx); if (r<=lo||hi<=l) return; if (l<=lo&&hi<=r){ t[idx].tag = val; push(idx); return; } int mi = (lo+hi) >> 1; update(l, r, val, ls, lo, mi); update(l, r, val, rs, mi, hi); pull(idx); } #undef ls #undef rs } seg; int hsh(vector<int> cur){ int res = 0; for (int i=0, p=1;i<n;i++, p=1ll*p*base % mod){ res = (res + 1ll*cur[i]*p) % mod; } return res; } vector<int> cross(vector<int> lhs, vector<int> rhs){ vector<int> cur(n); for (int i=0, p=1;i<n;i++, p = 1ll*p*base%mod){ int c; if (lhs[i]==rhs[i]) c = lhs[i]; else if (lhs[i]!=0&&rhs[i]!=0) c = 0; else if (lhs[i]!=1&&rhs[i]!=1) c = 1; else if (lhs[i]!=2&&rhs[i]!=2) c = 2; cur[i] = c; } return cur; } int32_t main(){ cin >> n; for (int k=0;k<3;k++){ scanf("%s", str); s[k].resize(n); for (int i=0;i<n;i++){ if (str[i]=='J') s[k][i] = 0; if (str[i]=='O') s[k][i] = 1; if (str[i]=='I') s[k][i] = 2; } } set<int> st; st.insert(hsh(s[0])); st.insert(hsh(s[1])); st.insert(hsh(s[2])); st.insert(hsh(cross(s[0],s[1]))); st.insert(hsh(cross(s[1],s[2]))); st.insert(hsh(cross(s[0],s[2]))); st.insert(hsh(cross(s[0],cross(s[1],s[2])))); st.insert(hsh(cross(s[1],cross(s[0],s[2])))); st.insert(hsh(cross(s[2],cross(s[0],s[1])))); scanf("%d", &Q); scanf("%s", str); for (int i=0;i<n;i++){ if (str[i]=='J') T[i] = 0; if (str[i]=='O') T[i] = 1; if (str[i]=='I') T[i] = 2; } seg.build(); if (st.find(seg.t[1].val)!=st.end()){ puts("Yes"); } else { puts("No"); } while (Q--){ int L, R; char C; scanf("%d %d %c", &L, &R, &C); int c=0; if (C=='J') c = 0; if (C=='O') c = 1; if (C=='I') c = 2; seg.update(L-1, R, c); int val = seg.t[1].val; if (st.find(val)!=st.end()){ puts("Yes"); } else { puts("No"); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 17436 KB | Output is correct |
2 | Correct | 95 ms | 17488 KB | Output is correct |
3 | Correct | 94 ms | 17492 KB | Output is correct |
4 | Incorrect | 86 ms | 17480 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 17436 KB | Output is correct |
2 | Correct | 95 ms | 17488 KB | Output is correct |
3 | Correct | 94 ms | 17492 KB | Output is correct |
4 | Incorrect | 86 ms | 17480 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 17436 KB | Output is correct |
2 | Correct | 95 ms | 17488 KB | Output is correct |
3 | Correct | 94 ms | 17492 KB | Output is correct |
4 | Incorrect | 86 ms | 17480 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 17436 KB | Output is correct |
2 | Correct | 95 ms | 17488 KB | Output is correct |
3 | Correct | 94 ms | 17492 KB | Output is correct |
4 | Incorrect | 86 ms | 17480 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |