Advertisement
bibaboba12345

Untitled

Jan 7th, 2023
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.52 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <bitset>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <random>
  7. #include <map>
  8. #include <set>
  9. #include <deque>
  10. #include <cassert>
  11. const int N = 2e6 + 7, A = 26, MOD = 1e9+7, C = 2;
  12. using namespace std;
  13. long long n, m;
  14.  
  15. struct Query {
  16. int i, j, i1, j1;
  17. };
  18.  
  19. vector<pair<int, int> > queried, sorted;
  20.  
  21. pair<int, int> getCoords(int ind) {
  22. return { queried[ind].first, queried[ind].second };
  23. }
  24. struct dsu {
  25. int p[N];
  26. int sz[N];
  27. int cnt_comps;
  28. int MinX[N], MaxX[N], MinY[N], MaxY[N];
  29. long long broken[N];
  30. bool good[N];
  31. void build(int n) {
  32. cnt_comps = 0;
  33. for (int i = 0; i < n; i++) {
  34. p[i] = i;
  35. sz[i] = 1;
  36. cnt_comps++;
  37. broken[i] = 0;
  38. auto c = getCoords(i);
  39. MinX[i] = c.first;
  40. MaxX[i] = c.first;
  41. MaxY[i] = c.second;
  42. MinY[i] = c.second;
  43. good[i] = 1;
  44. }
  45. }
  46. int get(int v) {
  47. if (p[v] == v) {
  48. return v;
  49. }
  50. p[v] = get(p[v]);
  51. return p[v];
  52. }
  53. void merge(int A, int B) {
  54. int a = get(A);
  55. int b = get(B);
  56. if (a == b) {
  57. broken[a]++;
  58. long long x = MaxX[a] - MinX[a] + 1;
  59. long long y = MaxY[a] - MinY[a] + 1;
  60. long long brk_nd = (x - 1) * y + (y - 1) * x;
  61. assert(broken[a] <= brk_nd);
  62. if (broken[a] == brk_nd) {
  63. cnt_comps++;
  64. good[a] = 1;
  65. }
  66. return;
  67. }
  68. if (sz[a] < sz[b]) {
  69. swap(a, b);
  70. }
  71. sz[a] += sz[b];
  72. p[b] = a;
  73. if (good[a]) {
  74. cnt_comps--;
  75. }
  76. if (good[b]) {
  77. cnt_comps--;
  78. }
  79. good[a] = 0;
  80. MinX[a] = min(MinX[a], MinX[b]);
  81. MinY[a] = min(MinY[a], MinY[b]);
  82. MaxX[a] = max(MaxX[a], MaxX[b]);
  83. MaxY[a] = max(MaxY[a], MaxY[b]);
  84. broken[a] += broken[b] + 1;
  85. long long x = MaxX[a] - MinX[a] + 1;
  86. long long y = MaxY[a] - MinY[a] + 1;
  87. long long brk_nd = (x - 1) * y + (y - 1) * x;
  88. assert(broken[a] <= brk_nd);
  89. if (broken[a] == brk_nd) {
  90. cnt_comps++;
  91. good[a] = 1;
  92. }
  93. }
  94. };
  95.  
  96. dsu D;
  97. vector<Query> qr;
  98.  
  99. int GetInd(int i, int j) {
  100. pair<int, int> s = { i,j };
  101. return lower_bound(queried.begin(), queried.end(), s) - queried.begin();
  102. }
  103.  
  104.  
  105. signed main()
  106. {
  107. #ifdef _DEBUG
  108. freopen("input.txt", "r", stdin);
  109. #else
  110. std::ios::sync_with_stdio(false);
  111. cin.tie(0);
  112. #endif
  113. cin >> n >> m;
  114. int q;
  115. cin >> q;
  116. for (int I = 0; I < q; I++) {
  117. int i1, j1, i2, j2;
  118. cin >> i1 >> j1 >> i2 >> j2;
  119. qr.push_back({ i1,j1,i2,j2 });
  120. sorted.push_back({ i1,j1 });
  121. sorted.push_back({ i2,j2 });
  122. }
  123. sort(sorted.begin(),sorted.end());
  124. queried.push_back(sorted[0]);
  125. for (int i = 1; i < sorted.size(); i++) {
  126. if (sorted[i] != sorted[i - 1]) {
  127. queried.push_back(sorted[i]);
  128. }
  129. }
  130.  
  131. long long untouched = ((long long)n) * m;
  132. untouched -= queried.size();
  133. D.build(queried.size());
  134. for (int I = 0; I < q; I++) {
  135. int i1, j1, i2, j2;
  136. i1 = qr[I].i;
  137. j1 = qr[I].j;
  138. i2 = qr[I].i1;
  139. j2 = qr[I].j1;
  140. D.merge(GetInd(i1, j1), GetInd(i2, j2));
  141. cout << D.cnt_comps + untouched << "\n";
  142. }
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement