Submission #106934

#TimeUsernameProblemLanguageResultExecution timeMemory
106934naoaiBoard (CEOI13_board)C++14
100 / 100
110 ms4500 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 + 5; const int inf = 1e6; struct str { int l0, l1; int lazy; } aint[4 * nmax + 1]; str uneste (str a, str b) { str aux; aux.lazy = -1; aux.l0 = max(a.l0, b.l0); aux.l1 = max(a.l1, b.l1); return aux; } void build (int nod, int x, int y) { aint[nod].l0 = aint[nod].l1 = -1; aint[nod].lazy = -1; if (x == y) return ; int mij = (x + y) / 2; build(2 * nod, x, mij); build(2 * nod + 1, mij + 1, y); } void update (int nod, int x, int y, int st, int dr, int val) { if (st <= x && y <= dr) { if (val == -1) { aint[nod].l0 = aint[nod].l1 = aint[nod].lazy = -1; } else { aint[nod].lazy = val; aint[nod].l0 = (val == 0 ? y : -1); aint[nod].l1 = (val == 1 ? y : -1); } return ; } int mij = (x + y) / 2; if (aint[nod].lazy != -1) { update(2 * nod, x, mij, x, mij, aint[nod].lazy); update(2 * nod + 1, mij + 1, y, mij + 1, y, aint[nod].lazy); aint[nod].lazy = -1; } if (st <= mij) update(2 * nod, x, mij, st, dr, val); if (mij < dr) update(2 * nod + 1, mij + 1, y, st, dr, val); aint[nod] = uneste(aint[2 * nod], aint[2 * nod + 1]); } vector<int> a, b; int get_val (int nod, int x, int y, int pos) { if (x == y) { return aint[nod].lazy; } int mij = (x + y) / 2; if (aint[nod].lazy != -1) { update(2 * nod, x, mij, x, mij, aint[nod].lazy); update(2 * nod + 1, mij + 1, y, mij + 1, y, aint[nod].lazy); aint[nod].lazy = -1; } if (pos <= mij) return get_val(2 * nod, x, mij, pos); else return get_val(2 * nod + 1, mij + 1, y, pos); } void constr_nr (vector<int> &v) { string s; cin >> s; build(1, 1, nmax); int cnt = 0; for (auto i : s) { if (i == 'U') { update(1, 1, nmax, cnt, cnt, -1); -- cnt; } else if (i == '1' || i == '2') { update(1, 1, nmax, cnt + 1, cnt + 1, i - '1'); ++ cnt; } else if (i == 'L') { int pos = aint[1].l1; update(1, 1, nmax, pos, pos, 0); if (pos + 1 <= cnt) update(1, 1, nmax, pos + 1, cnt, 1); } else { int pos = aint[1].l0; update(1, 1, nmax, pos, pos, 1); if (pos + 1 <= cnt) update(1, 1, nmax, pos + 1, cnt, 0); } } for (int i = 1; i <= cnt; ++ i) v.push_back(get_val(1, 1, nmax, i)); } int main () { constr_nr(a); constr_nr(b); int ans = a.size() + b.size(); int dif = 0; for (int i = 0; i < (int)a.size() && i < (int)b.size(); ++ i) { dif = 2 * dif + a[i] - b[i]; dif = min(dif, inf); ans = min(ans, abs(dif) + (int)a.size() + (int)b.size() - 2 * (i + 1)); } cout << ans << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...