Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #include <map>
- using namespace std;
- #define x first
- #define y second
- #define mp make_pair
- typedef pair <int, int> pii;
- const int N = 2e5 + 5;
- map <pair <int, int>, int> num;
- int mnx[N], mxx[N], mny[N], mxy[N], p[N], r[N], size[N];
- inline int getNum(pii pnt)
- {
- int sz = num.size();
- if (num[pnt]) return num[pnt];
- ++sz;
- num[pnt] = sz;
- mnx[sz] = mxx[sz] = pnt.x;
- mny[sz] = mxy[sz] = pnt.y;
- size[sz] = 0;
- p[sz] = sz;
- return sz;
- }
- inline bool isGood(int v)
- {
- long long area = 1LL * (mxx[v] - mnx[v] + 1) * (mxy[v] - mny[v]) + 1LL * (mxy[v] - mny[v] + 1) * (mxx[v] - mnx[v]);
- return area == size[v];
- }
- int root(int v) {return (v == p[v] ? v : p[v] = root(p[v]));}
- inline int join(int u, int v)
- {
- u = root(u);
- v = root(v);
- if (u == v)
- {
- size[u]++;
- return isGood(u);
- }
- int res = -isGood(u) - isGood(v);
- if (r[u] < r[v]) swap(u, v);
- p[v] = u;
- r[u] += r[u] == r[v];
- mnx[u] = min(mnx[u], mnx[v]);
- mxx[u] = max(mxx[u], mxx[v]);
- mny[u] = min(mny[u], mny[v]);
- mxy[u] = max(mxy[u], mxy[v]);
- size[u] += size[v] + 1;
- return res + isGood(u);
- }
- int n, m, k;
- long long ans;
- int main()
- {
- freopen("bestin.in", "r", stdin);
- freopen("bestin.out", "w", stdout);
- cin >> n >> m >> k;
- ans = 1LL * n * m;
- for (int i = 0; i < k; ++i)
- {
- int x1, y1, x2, y2;
- scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
- ans += join(getNum(mp(x1, y1)), getNum(mp(x2, y2)));
- printf("%I64d\n", ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment