//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; typedef pair<int, int> T; void solve(){ int n, m; cin >> n >> m; int k, q; cin >> k >> q; vector<T>p(k), que(q); for (auto &[x, y]: p) cin >> x >> y; for (auto &[x, y]: que) cin >> x >> y; vector<T>s; for (auto x: p) s.emplace_back(x); for (auto x: que) s.emplace_back(x); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); vector<int>X = {-1, 1, 0, 0}; vector<int>Y = {0, 0, 1, -1}; int N = (int)s.size(); vector<bool>active(N+1); auto get = [&](T x){ return (int)(lower_bound(s.begin(), s.end(), x)-s.begin()); }; for (auto x: p){ int i = get(x); active[i] = 1; } vector<vector<int>>neigh(N); for (int i = 0; i<N; i++){ for (int ck = 0; ck < 4; ck++){ T ss = {s[i].first+X[ck], s[i].second+Y[ck]}; int id = get(ss); if (id < (int)s.size() && s[id] == ss){ neigh[i].emplace_back(id); } else { neigh[i].emplace_back(N); } } } vector<bool>vis(N); auto answer = [&](){ queue<int>qq; vis.assign(N, 0); for (int i = 0; i<N; i++){ if (!active[i]) continue; // debug(s[i], neigh[i]); if ((!active[neigh[i][0]] && !active[neigh[i][1]]) || (!active[neigh[i][2]] && !active[neigh[i][3]])) { qq.push(i); // debug(s[i]); vis[i] = 1; } } int ans = 0; while ((int)qq.size()){ auto i = qq.front();qq.pop(); // debug(s[i]); ans++; for (auto j: neigh[i]){ if (j == N || vis[j] || !active[j]) continue; //nieaktywny lub odwiedzony bool left = (!active[neigh[j][0]] || vis[neigh[j][0]]); bool right = (!active[neigh[j][1]] || vis[neigh[j][1]]); if (left && right){ vis[j] = 1; qq.push(j); continue; } left = (!active[neigh[j][2]] || vis[neigh[j][2]]); right = (!active[neigh[j][3]] || vis[neigh[j][3]]); if (left && right){ vis[j] = 1; qq.push(j); } } } cout << ans << "\n"; }; answer(); for (auto punkt: que){ int i = get(punkt); active[i] = 1-active[i]; answer(); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | //Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; typedef pair<int, int> T; void solve(){ int n, m; cin >> n >> m; int k, q; cin >> k >> q; vector<T>p(k), que(q); for (auto &[x, y]: p) cin >> x >> y; for (auto &[x, y]: que) cin >> x >> y; vector<T>s; for (auto x: p) s.emplace_back(x); for (auto x: que) s.emplace_back(x); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); vector<int>X = {-1, 1, 0, 0}; vector<int>Y = {0, 0, 1, -1}; int N = (int)s.size(); vector<bool>active(N+1); auto get = [&](T x){ return (int)(lower_bound(s.begin(), s.end(), x)-s.begin()); }; for (auto x: p){ int i = get(x); active[i] = 1; } vector<vector<int>>neigh(N); for (int i = 0; i<N; i++){ for (int ck = 0; ck < 4; ck++){ T ss = {s[i].first+X[ck], s[i].second+Y[ck]}; int id = get(ss); if (id < (int)s.size() && s[id] == ss){ neigh[i].emplace_back(id); } else { neigh[i].emplace_back(N); } } } vector<bool>vis(N); auto answer = [&](){ queue<int>qq; vis.assign(N, 0); for (int i = 0; i<N; i++){ if (!active[i]) continue; // debug(s[i], neigh[i]); if ((!active[neigh[i][0]] && !active[neigh[i][1]]) || (!active[neigh[i][2]] && !active[neigh[i][3]])) { qq.push(i); // debug(s[i]); vis[i] = 1; } } int ans = 0; while ((int)qq.size()){ auto i = qq.front();qq.pop(); // debug(s[i]); ans++; for (auto j: neigh[i]){ if (j == N || vis[j] || !active[j]) continue; //nieaktywny lub odwiedzony bool left = (!active[neigh[j][0]] || vis[neigh[j][0]]); bool right = (!active[neigh[j][1]] || vis[neigh[j][1]]); if (left && right){ vis[j] = 1; qq.push(j); continue; } left = (!active[neigh[j][2]] || vis[neigh[j][2]]); right = (!active[neigh[j][3]] || vis[neigh[j][3]]); if (left && right){ vis[j] = 1; qq.push(j); } } } cout << ans << "\n"; }; answer(); for (auto punkt: que){ int i = get(punkt); active[i] = 1-active[i]; answer(); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; } |