#include <bits/stdc++.h> #define fi first #define sc second #define pb push_back #define rep(i,p,k) for(int i=(p);i<(k);++i) #define forn(i,p,k) for(int i=(p);i<=(k);++i) #define forr(i,k,p) for(int i=(k)-1;i>=(p);--i) #define each(a,b) for(auto&a:b) #define all(v) begin(v), end(v) #define RET(smth) return void(cout<<(smth)<<'\n'); #define sz(v) (int)v.size() using namespace std; using pii = pair<int,int>; using ll = long long; using lll = __int128_t; using Vi = vector<int>; #ifdef DEBUG #include "debug.h" #else #define debug(...) ; #endif struct hsh { size_t operator()(pii x) const { return 1ll*x.fi*200013 + x.sc; } }; unordered_set<pii, hsh> S; bool rem(int x) { return (x&12) == 0 || (x&3) == 0; } int sim() { int res = 0; unordered_map<pii, int, hsh> C; vector<pii> toe, tmp; for(auto [x, y] : S) { int d = S.count({x-1,y})*8 + S.count({x+1,y})*4 + S.count({x,y-1})*2 + S.count({x,y+1}); debug(x,y,d); if(rem(d)) toe.emplace_back(x,y); else C.emplace(pii{x,y}, d); } debug(toe); debug(C); auto handle = [&](int x, int y, int dr) { auto it = C.find({x,y}); if(it == C.end()) return; int &d = it->second; if(rem(d)) return; d -= dr; if(rem(d)) tmp.emplace_back(x,y); }; for(;!toe.empty();toe.swap(tmp), tmp.clear()) { for(auto [x,y] : toe) { res++; handle(x+1,y,8); handle(x-1,y,4); handle(x,y+1,2); handle(x,y-1,1); debug(x,y,C); } } return res; } int main() { #ifndef DEBUG cin.tie(0) -> sync_with_stdio(0); #endif int n,m,k,q; cin >> n >> m >> k >> q; rep(i,0,k) { int x,y; cin >> x >> y; S.insert({x,y}); } cout << sim() << '\n'; rep(i,0,q) { int x,y; cin >> x >> y; auto it = S.find({x,y}); if(it == S.end()) { S.insert({x,y}); } else { S.erase(it); } cout << sim() << '\n'; } 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 | #include <bits/stdc++.h> #define fi first #define sc second #define pb push_back #define rep(i,p,k) for(int i=(p);i<(k);++i) #define forn(i,p,k) for(int i=(p);i<=(k);++i) #define forr(i,k,p) for(int i=(k)-1;i>=(p);--i) #define each(a,b) for(auto&a:b) #define all(v) begin(v), end(v) #define RET(smth) return void(cout<<(smth)<<'\n'); #define sz(v) (int)v.size() using namespace std; using pii = pair<int,int>; using ll = long long; using lll = __int128_t; using Vi = vector<int>; #ifdef DEBUG #include "debug.h" #else #define debug(...) ; #endif struct hsh { size_t operator()(pii x) const { return 1ll*x.fi*200013 + x.sc; } }; unordered_set<pii, hsh> S; bool rem(int x) { return (x&12) == 0 || (x&3) == 0; } int sim() { int res = 0; unordered_map<pii, int, hsh> C; vector<pii> toe, tmp; for(auto [x, y] : S) { int d = S.count({x-1,y})*8 + S.count({x+1,y})*4 + S.count({x,y-1})*2 + S.count({x,y+1}); debug(x,y,d); if(rem(d)) toe.emplace_back(x,y); else C.emplace(pii{x,y}, d); } debug(toe); debug(C); auto handle = [&](int x, int y, int dr) { auto it = C.find({x,y}); if(it == C.end()) return; int &d = it->second; if(rem(d)) return; d -= dr; if(rem(d)) tmp.emplace_back(x,y); }; for(;!toe.empty();toe.swap(tmp), tmp.clear()) { for(auto [x,y] : toe) { res++; handle(x+1,y,8); handle(x-1,y,4); handle(x,y+1,2); handle(x,y-1,1); debug(x,y,C); } } return res; } int main() { #ifndef DEBUG cin.tie(0) -> sync_with_stdio(0); #endif int n,m,k,q; cin >> n >> m >> k >> q; rep(i,0,k) { int x,y; cin >> x >> y; S.insert({x,y}); } cout << sim() << '\n'; rep(i,0,q) { int x,y; cin >> x >> y; auto it = S.find({x,y}); if(it == S.end()) { S.insert({x,y}); } else { S.erase(it); } cout << sim() << '\n'; } return 0; } |