Codeforces Round 878 (Div. 3) - E. Character Blocking (1600)
계속 자료구조에 $s_{1, i} \neq s_{2, i}$ 인 $i$ 들을 관리하면 된다.
그냥 구현 문제이다.
그리고 $3$번 쿼리에서 자료구조가 비어있는지를 검사하면 된다.
잠시 block 시키는 쿼리는 지금 $i$ 가 서로 다르다면 자료구조에서 그걸 삭제해주고 현재 시간 $+ t$ 에 다시 삽입해준다.
void solve() {
string s1, s2;
cin >> s1 >> s2;
int t, q;
cin >> t >> q;
set<int> diff;
int n = sz(s1);
for (int i = 0; i < n; i++) if (s1[i] ^ s2[i])diff.insert(i);
map<int, vi> restore;
int sec = 0;
while (q--) {
for (int i: restore[sec]) {
if (s1[i] != s2[i]) diff.insert(i);
}
int c;
cin >> c;
if (c == 1) {
int i;
cin >> i;
i--;
restore[sec + t].pb(i);
if (s1[i] != s2[i]) diff.erase(i);
} else if (c == 2) {
int t1, i1, t2, i2;
cin >> t1 >> i1 >> t2 >> i2, i1--, i2--;
if (t1 == 2 && t2 == 1) swap(t1, t2), swap(i1, i2);
if (s1[i1] ^ s2[i1]) diff.erase(i1);
if (s1[i2] ^ s2[i2]) diff.erase(i2);
if (t1 == 1 && t2 == 1)swap(s1[i1], s1[i2]);
else if (t1 == 1 && t2 == 2) swap(s1[i1], s2[i2]);
else swap(s2[i1], s2[i2]);
if (s1[i1] ^ s2[i1]) diff.insert(i1);
if (s1[i2] ^ s2[i2]) diff.insert(i2);
} else {
if (sz(diff) == 0) cout << "YES\n";
else cout << "NO\n";
}
debug(s1, s2);
sec++;
}
}
Comments