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
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7ZgrFU
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!