Guest User

Untitled

a guest
Nov 19th, 2012
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. using namespace std;
  7.  
  8. #define x first
  9. #define y second
  10. #define mp make_pair
  11. typedef pair <int, int> pii;
  12. const int N = 2e5 + 5;
  13.  
  14. map <pair <int, int>, int> num;
  15. int mnx[N], mxx[N], mny[N], mxy[N], p[N], r[N], size[N];
  16.  
  17. inline int getNum(pii pnt)
  18. {
  19.   int sz = num.size();
  20.   if (num[pnt]) return num[pnt];
  21.   ++sz;
  22.   num[pnt] = sz;
  23.   mnx[sz] = mxx[sz] = pnt.x;
  24.   mny[sz] = mxy[sz] = pnt.y;
  25.   size[sz] = 0;
  26.   p[sz] = sz;
  27.   return sz;
  28. }
  29. inline bool isGood(int v)
  30. {
  31.   long long area = 1LL * (mxx[v] - mnx[v] + 1) * (mxy[v] - mny[v]) + 1LL * (mxy[v] - mny[v] + 1) * (mxx[v] - mnx[v]);
  32.   return area == size[v];
  33. }
  34. int root(int v) {return (v == p[v] ? v : p[v] = root(p[v]));}
  35. inline int join(int u, int v)
  36. {
  37.   u = root(u);
  38.   v = root(v);
  39.   if (u == v)
  40.   {
  41.     size[u]++;
  42.     return isGood(u);
  43.   }
  44.   int res = -isGood(u) - isGood(v);
  45.   if (r[u] < r[v]) swap(u, v);
  46.   p[v] = u;
  47.   r[u] += r[u] == r[v];
  48.   mnx[u] = min(mnx[u], mnx[v]);
  49.   mxx[u] = max(mxx[u], mxx[v]);
  50.   mny[u] = min(mny[u], mny[v]);
  51.   mxy[u] = max(mxy[u], mxy[v]);
  52.   size[u] += size[v] + 1;
  53.   return res + isGood(u);
  54. }
  55. int n, m, k;
  56. long long ans;
  57. int main()
  58. {
  59.   freopen("bestin.in", "r", stdin);
  60.   freopen("bestin.out", "w", stdout);
  61.   cin >> n >> m >> k;
  62.   ans = 1LL * n * m;
  63.   for (int i = 0; i < k; ++i)
  64.   {
  65.     int x1, y1, x2, y2;
  66.     scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  67.     ans += join(getNum(mp(x1, y1)), getNum(mp(x2, y2)));
  68.     printf("%I64d\n", ans);
  69.   }
  70.   return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment