Submission #1221882

#TimeUsernameProblemLanguageResultExecution timeMemory
1221882TrustfulcomicCrossing (JOI21_crossing)C++20
26 / 100
5510 ms84108 KiB
#include<bits/stdc++.h> using namespace std; struct node { char value = 'X'; char lazy = 'X'; bool same_ch = true; vector<bool> good = vector<bool>(9, true); }; vector<vector<node>> int_ref(1); void res_laz(int cur, vector<node>& intervalac) { node& nd = intervalac[cur]; vector<node> ref_nds; for (int j = 0; j<int_ref.size(); j++){ ref_nds.push_back(int_ref[j][cur]); } if (cur < intervalac.size()/2) { node& l_ch = intervalac[2*cur]; node& r_ch = intervalac[2*cur+1]; if (nd.lazy != 'X') { nd.value = nd.lazy; l_ch.lazy = nd.lazy; r_ch.lazy = nd.lazy; nd.lazy = 'X'; nd.same_ch = true; for (int j = 0; j<int_ref.size(); j++) { if (!ref_nds[j].same_ch) { nd.good[j] = false; } else if (nd.value == ref_nds[j].value) { nd.good[j] = true; } else { nd.good[j] = false; } } } } else { if (nd.lazy != 'X') { nd.value = nd.lazy; nd.lazy = 'X'; } nd.same_ch = true; for (int j = 0; j<int_ref.size(); j++) { if (!ref_nds[j].same_ch) { nd.good[j] = false; } else if (nd.value == ref_nds[j].value) { nd.good[j] = true; } else { nd.good[j] = false; } } } } void resolve(int cur, vector<node>& intervalac) { node& nd = intervalac[cur]; vector<node> ref_nds; for (int j = 0; j<int_ref.size(); j++){ ref_nds.push_back(int_ref[j][cur]); } if (cur < intervalac.size()/2) { node& l_ch = intervalac[2*cur]; node& r_ch = intervalac[2*cur+1]; if (nd.lazy != 'X') { nd.value = nd.lazy; l_ch.lazy = nd.lazy; r_ch.lazy = nd.lazy; nd.lazy = 'X'; nd.same_ch = true; for (int j = 0; j<int_ref.size(); j++) { if (!ref_nds[j].same_ch) { nd.good[j] = false; } else if (nd.value == ref_nds[j].value) { nd.good[j] = true; } else { nd.good[j] = false; } } } else { res_laz(2*cur, intervalac); res_laz(2*cur+1, intervalac); if (l_ch.value == r_ch.value && l_ch.same_ch && r_ch.same_ch) { nd.value = l_ch.value; nd.same_ch = true; for (int j = 0; j<int_ref.size(); j++) { if (!ref_nds[j].same_ch) { nd.good[j] = false; } else if (nd.value == ref_nds[j].value) { nd.good[j] = true; } else { nd.good[j] = false; } } } else { nd.value = 'X'; nd.same_ch = false; for (int j = 0; j<int_ref.size(); j++) { if (l_ch.good[j] && r_ch.good[j]) { nd.good[j] = true; } else { nd.good[j] = false; } } } } } else { if (nd.lazy != 'X') { nd.value = nd.lazy; nd.lazy = 'X'; } nd.same_ch = true; for (int j = 0; j<int_ref.size(); j++) { if (!ref_nds[j].same_ch) { nd.good[j] = false; } else if (nd.value == ref_nds[j].value) { nd.good[j] = true; } else { nd.good[j] = false; } } } } void update(int cur, int a, int b, int l, int r, char val, vector<node>& intervalac) { resolve(cur, intervalac); if (a == l && b == r) { intervalac[cur].lazy = val; } else if (b <= (l+r)/2) { update(2*cur, a, b, l, (l+r)/2, val, intervalac); } else if (a >= (l+r)/2) { update(2*cur+1, a, b, (l+r)/2, r, val, intervalac); } else { update(2*cur, a, (l+r)/2, l, (l+r)/2, val, intervalac); update(2*cur+1, (l+r)/2, b, (l+r)/2, r, val, intervalac); } resolve(cur, intervalac); } string cross(string& a, string& b) { string r = ""; for (int i = 0; i<a.size(); i++) { if (a[i] == b[i]) { r += a[i]; } else { r += 73 + 74 + 79 - a[i] - b[i]; } } return r; } vector<string> gen_all(vector<string> start) { set<string> st_set; for (string& s : start) { st_set.insert(s); } vector<string> s; for (const string& str : st_set) { s.push_back(str); } while (true) { set<string> new_s_set; vector<string> new_s; for (int i = 0; i<s.size(); i++) { for (int j = i+1; j<s.size(); j++) { string cr = cross(s[i], s[j]); if (new_s_set.find(cr) == new_s_set.end()) { new_s.push_back(cr); new_s_set.insert(cr); } } } for (string& str : s) { if (new_s_set.find(str) == new_s_set.end()) { new_s.push_back(str); new_s_set.insert(str); } } if (s.size() == new_s.size()) break; s = new_s; } return s; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; string s1,s2,s3; cin >> s1 >> s2 >> s3; int q; cin >> q; string start_cur; cin >> start_cur; int i_size = 1; while (i_size < n) i_size *= 2; i_size *= 2; vector<node> int_cur(i_size); int_ref[0].resize(i_size); for (int i = 0; i < i_size/2; i++) { if (i < s1.size()) { update(1, i, i+1, 0, i_size/2, s1[i], int_ref[0]); update(1, i, i+1, 0, i_size/2, start_cur[i], int_cur); } else { update(1, i, i+1, 0, i_size/2, 'Z', int_ref[0]); update(1, i, i+1, 0, i_size/2, 'Z', int_cur); } } vector<bool> res(q+1); res[0] = int_cur[1].good[0]; for (int i = 1; i<q+1; i++) { int a,b; cin >> a >> b; a--; char v; cin >> v; update(1, a, b, 0, i_size/2, v, int_cur); res[i] = int_cur[1].good[0]; } for (bool b : res) { if (b) { cout << "Yes\n"; } else { cout << "No\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...