Submission #954463

#TimeUsernameProblemLanguageResultExecution timeMemory
954463GrandTiger1729Bliskost (COI23_bliskost)C++17
57 / 100
1058 ms295224 KiB
#include <bits/stdc++.h> using namespace std; const int K = 26; struct SegTree { int l, r, mid; SegTree *lc, *rc; int val[K]{}; SegTree(const vector<int> &a, int l_, int r_) : l(l_), r(r_) { mid = (l + r) / 2; if (l == r - 1) { for (int j = 0; j < K; j++) { val[j] = (a[l] - j + K) % K; } return; } lc = new SegTree(a, l, mid); rc = new SegTree(a, mid, r); pull(); } void pull() { for (int i = 0; i < K; i++) { val[i] = rc->val[lc->val[i]]; } } void update(int i, int u) { if (l == r - 1) { for (int j = 0; j < K; j++) { val[j] = (u - j + K) % K; } return; } if (i < mid) { lc->update(i, u); } else { rc->update(i, u); } pull(); } void query(int &cur, int ll, int rr) { if (ll <= l && rr >= r) { cur = val[cur]; return; } if (ll < mid) { lc->query(cur, ll, rr); } if (mid < rr) { rc->query(cur, ll, rr); } } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin >> n >> q; string a, b; cin >> a >> b; vector<int> c(n); for (int i = 0; i < n; i++) { c[i] = (b[i] - a[i] + K) % K; } SegTree st(c, 0, n); int cur = 0; st.query(cur, 0, n); cout << (cur == 0 ? "da" : "ne") << '\n'; while (q--) { int j; char x; cin >> j >> x; j--; a[j] = x; st.update(j, (b[j] - a[j] + K) % K); cur = 0; st.query(cur, 0, n); cout << (cur == 0 ? "da" : "ne") << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...