fork download
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. typedef long double ld;
  6. typedef unsigned int ui32;
  7. const long long INFLL = 1e18;
  8.  
  9. using namespace std;
  10.  
  11. const short MAXN = 15000;
  12.  
  13. class Coord {
  14. public:
  15. vector<short> vec;
  16.  
  17. Coord(short x) {
  18. vec.push_back(x);
  19. }
  20.  
  21. Coord(const vector<short> &vec) : vec(move(vec)) {}
  22.  
  23. bool operator==(const Coord &lhs) {
  24. if (vec.size() != lhs.vec.size()) {
  25. return false;
  26. }
  27. for (int i = 0; i < (int)vec.size(); i++) {
  28. if (vec[i] != lhs.vec[i]) {
  29. return false;
  30. }
  31. }
  32. return true;
  33. }
  34.  
  35. Coord operator+(const Coord &lhs) {
  36. vector<short> res;
  37. int l = 0, r = 0;
  38.  
  39. while (l < (int)vec.size() && r < (int)lhs.vec.size()) {
  40. short nw;
  41. if (vec[l] == lhs.vec[r]) {
  42. nw = vec[l] + 1;
  43. ++l;
  44. ++r;
  45. } else if (vec[l] < lhs.vec[r]) {
  46. nw = vec[l];
  47. ++l;
  48. } else {
  49. nw = lhs.vec[r];
  50. ++r;
  51. }
  52.  
  53. if (res.empty() || res.back() != nw) {
  54. res.push_back(nw);
  55. } else {
  56. ++res.back();
  57. }
  58. }
  59.  
  60. while (l < (int)vec.size()) {
  61. short nw = vec[l];
  62. ++l;
  63.  
  64. if (res.empty() || res.back() != nw) {
  65. res.push_back(nw);
  66. } else {
  67. ++res.back();
  68. }
  69. }
  70.  
  71. while (r < (int)lhs.vec.size()) {
  72. short nw = lhs.vec[r];
  73. ++r;
  74.  
  75. if (res.empty() || res.back() != nw) {
  76. res.push_back(nw);
  77. } else {
  78. ++res.back();
  79. }
  80. }
  81.  
  82. return Coord(res);
  83. }
  84.  
  85. bool operator<=(const Coord &lhs) {
  86. int l = (int)vec.size() - 1;
  87. int r = (int)lhs.vec.size() - 1;
  88.  
  89. while (l >= 0 && r >= 0) {
  90. if (vec[l] != lhs.vec[r]) {
  91. return vec[l] < lhs.vec[r];
  92. }
  93. --l;
  94. --r;
  95. }
  96.  
  97. return l == -1;
  98. }
  99.  
  100. bool operator>=(const Coord &lhs) {
  101. int l = (int)vec.size() - 1;
  102. int r = (int)lhs.vec.size() - 1;
  103.  
  104. while (l >= 0 && r >= 0) {
  105. if (vec[l] != lhs.vec[r]) {
  106. return vec[l] > lhs.vec[r];
  107. }
  108. --l;
  109. --r;
  110. }
  111.  
  112. return r == -1;
  113. }
  114.  
  115. void dec() {
  116. for (auto &x : vec) {
  117. if (x > 0) {
  118. --x;
  119. }
  120. }
  121. }
  122. };
  123.  
  124. struct rect {
  125. Coord x1, y1, x2, y2;
  126. };
  127.  
  128. vector<rect> vec;
  129. int cnt;
  130.  
  131. void go(Coord &x1, Coord &y1, Coord &x2, Coord &y2) {
  132. int x;
  133. cin >> x;
  134. if (x == 0) {
  135. return;
  136. } else if (x == 1) {
  137. ++cnt;
  138. vec.push_back({ x1, y1, x2, y2 });
  139. } else {
  140. Coord midX = (x1 + x2);
  141. midX.dec();
  142. Coord midY = (y1 + y2);
  143. midY.dec();
  144.  
  145. go(x1, midY, midX, y2);
  146. go(midX, midY, x2, y2);
  147. go(midX, y1, x2, midY);
  148. go(x1, y1, midX, midY);
  149. }
  150. }
  151.  
  152. int col[MAXN + 1], p[MAXN + 1], sz[MAXN + 1];
  153.  
  154. int get(int x) {
  155. return x == p[x] ? x : p[x] = get(p[x]);
  156. }
  157.  
  158. void Union(int a, int b) {
  159. a = get(a);
  160. b = get(b);
  161.  
  162. if (a != b) {
  163. if (sz[a] < sz[b]) {
  164. swap(a, b);
  165. }
  166. sz[a] += sz[b];
  167. p[b] = a;
  168. }
  169. }
  170.  
  171.  
  172. int main() {
  173. ios_base::sync_with_stdio(false);
  174. cin.tie(0);
  175. //freopen("input.txt", "r", stdin);
  176. //freopen("input.txt", "w", stdout);
  177.  
  178. Coord x1(0), y1(0), x2(MAXN), y2(MAXN);
  179. go(x1, y1, x2, y2);
  180.  
  181. int ans = (int)vec.size();
  182.  
  183. for (int i = 0; i < ans; i++) {
  184. p[i] = i;
  185. sz[i] = 1;
  186. }
  187.  
  188. for (int i = 0; i < (int)vec.size(); i++) {
  189. /*for (auto x : vec[i].x1.vec) {
  190.   cout << x << " ";
  191.   }
  192.   cout << "\n";
  193.   for (auto x : vec[i].y1.vec) {
  194.   cout << x << " ";
  195.   }
  196.   cout << "\n";
  197.   for (auto x : vec[i].x2.vec) {
  198.   cout << x << " ";
  199.   }
  200.   cout << "\n";
  201.   for (auto x : vec[i].y2.vec) {
  202.   cout << x << " ";
  203.   }
  204.   cout << "\n\n\n";*/
  205.  
  206. for (int j = i - 1; j >= 0; j--) {
  207. if (vec[j].y1 == vec[i].y2) {
  208. if (!(vec[j].x2 <= vec[i].x1 || vec[j].x1 >= vec[i].x2)) {
  209. if (get(i) != get(j)) {
  210. --ans;
  211. Union(i, j);
  212. continue;
  213. }
  214. }
  215. }
  216. if (vec[j].y2 == vec[i].y1) {
  217. if (!(vec[j].x2 <= vec[i].x1 || vec[j].x1 >= vec[i].x2)) {
  218. if (get(i) != get(j)) {
  219. --ans;
  220. Union(i, j);
  221. continue;
  222. }
  223. }
  224. }
  225. if (vec[j].x2 == vec[i].x1) {
  226. if (!(vec[j].y2 <= vec[i].y1 || vec[j].y1 >= vec[i].y2)) {
  227. if (get(i) != get(j)) {
  228. --ans;
  229. Union(i, j);
  230. continue;
  231. }
  232. }
  233. }
  234. if (vec[j].x1 == vec[i].x2) {
  235. if (!(vec[j].y2 <= vec[i].y1 || vec[j].y1 >= vec[i].y2)) {
  236. if (get(i) != get(j)) {
  237. --ans;
  238. Union(i, j);
  239. continue;
  240. }
  241. }
  242. }
  243. }
  244. }
  245.  
  246. cout << ans << "\n";
  247. return 0;
  248. }
Time limit exceeded #stdin #stdout 5s 2984148KB
stdin
Standard input is empty
stdout
Standard output is empty