fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define PhTrNghia "minhomes"
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5 + 5;
  9. const int inf = 1e18;
  10.  
  11. struct DSU{
  12.     int n;
  13.     vector <int> parent, sz;
  14.     DSU(int _n){
  15.         n =_n;
  16.         parent.assign(n + 5, 0);
  17.         sz.assign(n + 5, 0);
  18.         for (int i = 1; i <= n; i++){
  19.             parent[i] = i;
  20.             sz[i] = 1;
  21.         }
  22.     }
  23.  
  24.     int find_parent(int u){
  25.         if (u == parent[u]) return u;
  26.         return parent[u] = find_parent(parent[u]);
  27.     }
  28.  
  29.     bool Union(int u, int v){
  30.         u = find_parent(u);
  31.         v = find_parent(v);
  32.         if (u == v) return 0;
  33.         if (sz[u] < sz[v]) swap(u, v);
  34.         sz[u] += sz[v];
  35.         parent[v] = u;
  36.         return 1;
  37.     }
  38. };
  39.  
  40. struct phtrnghia{
  41.     int type, x, y;
  42. };
  43.  
  44. bool cmp(phtrnghia x, phtrnghia y){
  45.     return x.x < y.x;
  46. }
  47.  
  48. bool in(int l, int pos, int r){
  49.     return (l <= pos && pos <= r);
  50. }
  51.  
  52. bool overlap(phtrnghia a, phtrnghia b){
  53.     bool c1 = (a.x <= b.x && b.x <= a.y);
  54.     bool c2 = (a.x <= b.y && b.y <= a.y);
  55.     bool c3 = (b.x <= a.x && a.x <= b.y);
  56.     bool c4 = (b.x <= a.y && a.y <= b.y);
  57.     return (c1 or c2 or c3 or c4);
  58. }
  59.  
  60. int n, m, q, cc;
  61. int ans[maxn], pre[maxn], pref[maxn], res[maxn], pointer_col[maxn], mark[maxn];
  62. vector <phtrnghia> close_col[maxn], row[maxn], col[maxn], col_close[maxn], col_open[maxn];
  63.  
  64. signed main(){
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(0); cout.tie(0);
  67.     if (fopen(PhTrNghia".INP", "r")){
  68.         freopen(PhTrNghia".INP", "r", stdin);
  69.         freopen(PhTrNghia".OUT", "w", stdout);
  70.     }
  71.  
  72.     cin >> n >> m >> q;
  73.     cc = q;
  74.     for (int i = 1; i <= q; i++){
  75.         int x1, y1, x2, y2;
  76.         cin >> x1 >> y1 >> x2 >> y2; //line
  77.         pre[x1]++;
  78.         if (x1 == x2){
  79.             row[x1].push_back({i, y1, y2});
  80.             pref[x1] += (y2 - y1 + 1);
  81.             pref[x1+1] -= (y2 - y1 + 1);
  82.         }
  83.  
  84.         if (x1 == x2 && y1 == y2) continue;
  85.  
  86.         if (y1 == y2){
  87.             col_open[x1].push_back({i, y1, y2});
  88.             col_close[x2+1].push_back({i, y1, y2});
  89.  
  90.             col[y1].push_back({i, x1, x2});
  91.  
  92.             close_col[x2].push_back({i, y1, y2});
  93.  
  94.             pref[x1]++;
  95.             pref[x2+1]--;
  96.         }
  97.     }
  98.  
  99.     for (int i = 1; i <= n; i++){
  100.         pre[i] += pre[i-1];
  101.         pref[i] += pref[i-1];
  102.         res[i] = res[i-1] + pref[i];
  103.         sort(row[i].begin(), row[i].end(), cmp);
  104.         sort(col_open[i].begin(), col_open[i].end(), cmp);
  105.         sort(close_col[i].begin(), close_col[i].end(), cmp);
  106.         sort(col[i].begin(), col[i].end(), cmp);
  107.     }
  108.  
  109.     DSU dsu(q);
  110.  
  111.     for (int i = 1; i <= n; i++){
  112.  
  113.         int idx3 = 0, idx4 = 0;
  114.  
  115.         for (phtrnghia cur: col_close[i]){
  116.             int pos = cur.x;
  117.             mark[pos] = 0;
  118.         }
  119.  
  120.         for (phtrnghia cur: col_open[i]){
  121.             int shape = cur.type;
  122.             int pos = cur.x;
  123.  
  124.             while (idx3 < row[i-1].size() && row[i-1][idx3].y <= pos){
  125.                 if (in(row[i-1][idx3].x, pos, row[i-1][idx3].y)) cc -= dsu.Union(shape, row[i-1][idx3].type);
  126.                 idx3++;
  127.             }
  128.             if (idx3 < row[i-1].size() && in(row[i-1][idx3].x, pos, row[i-1][idx3].y)) cc -= dsu.Union(shape, row[i-1][idx3].type);
  129.  
  130.             while (idx4 < close_col[i-1].size() && close_col[i-1][idx4].y <= pos){
  131.                 if (in(close_col[i-1][idx4].x, pos, close_col[i-1][idx4].y)) cc -= dsu.Union(shape, close_col[i-1][idx4].type);
  132.                 idx4++;
  133.             }
  134.             if (idx4 < close_col[i-1].size() && in(close_col[i-1][idx4].x, pos, close_col[i-1][idx4].y)) cc -= dsu.Union(shape, close_col[i-1][idx4].type);
  135.  
  136.             if (mark[pos-1]) cc -= dsu.Union(shape, mark[pos-1]);
  137.             if (mark[pos+1]) cc -= dsu.Union(shape, mark[pos+1]);
  138.             mark[pos] = shape;
  139.         }
  140.  
  141.  
  142.         int old_shape = inf, old_r = inf, idx1 = 0, idx2 = 0;
  143.         for (phtrnghia cur: row[i]){
  144.             int shape = cur.type;
  145.             int L = cur.x;
  146.             int R = cur.y;
  147.  
  148.             if (old_r+1 == cur.x) cc -= dsu.Union(shape, old_shape);
  149.  
  150.             while (idx1 < row[i-1].size() && row[i-1][idx1].y <= cur.y){
  151.                 if (overlap(cur, row[i-1][idx1])) cc -= dsu.Union(shape, row[i-1][idx1].type);
  152.                 idx1++;
  153.             }
  154.  
  155.             if (idx1 < row[i-1].size() && overlap(cur, row[i-1][idx1])) cc -= dsu.Union(shape, row[i-1][idx1].type);
  156.  
  157.             while (idx2 < close_col[i-1].size() && close_col[i-1][idx2].y <= cur.y){
  158.                 if (overlap(cur, close_col[i-1][idx2])) cc -= dsu.Union(shape, close_col[i-1][idx2].type);
  159.                 idx2++;
  160.             }
  161.             if (idx2 < close_col[i-1].size() && overlap(cur, close_col[i-1][idx2])) cc -= dsu.Union(shape, close_col[i-1][idx2].type);
  162.  
  163.             while (pointer_col[L-1] < col[L-1].size() && col[L-1][pointer_col[L-1]].y <= i){
  164.                 if (in(col[L-1][pointer_col[L-1]].x, i, col[L-1][pointer_col[L-1]].y)) cc -= dsu.Union(shape, col[L-1][pointer_col[L-1]].type);
  165.                 pointer_col[L-1]++;
  166.             }
  167.             if (pointer_col[L-1] < col[L-1].size() && in(col[L-1][pointer_col[L-1]].x, i, col[L-1][pointer_col[L-1]].y)) cc -= dsu.Union(shape, col[L-1][pointer_col[L-1]].type);
  168.  
  169.             while (pointer_col[R+1] < col[R+1].size() && col[R+1][pointer_col[R+1]].y <= i){
  170.                 if (in(col[R+1][pointer_col[R+1]].x, i, col[R+1][pointer_col[R+1]].y)) cc -= dsu.Union(shape, col[R+1][pointer_col[R+1]].type);
  171.                 pointer_col[R+1]++;
  172.             }
  173.             if (pointer_col[R+1] < col[R+1].size() && in(col[R+1][pointer_col[R+1]].x, i, col[R+1][pointer_col[R+1]].y)) cc -= dsu.Union(shape, col[R+1][pointer_col[R+1]].type);
  174.  
  175.             old_shape = shape;
  176.             old_r = cur.y;
  177.         }
  178.  
  179.         ans[i] = cc - (pre[n] - pre[i]);
  180.         cout << res[i] << " " << ans[i] << endl;
  181.     }
  182.  
  183.     return 0;
  184. }
  185. /*
  186. 4 3 4
  187. 1 1 1 2
  188. 3 1 3 2
  189. 1 3 2 3
  190. 4 1 4 3
  191.  
  192. 5 5 7
  193. 1 2 1 3
  194. 2 1 2 2
  195. 1 4 2 4
  196. 2 5 3 5
  197. 3 3 3 4
  198. 4 2 4 3
  199. 4 4 4 5
  200.  
  201. 6 3 3
  202. 1 1 1 3
  203. 2 2 5 2
  204. 6 1 6 3
  205. */
  206.  
Success #stdin #stdout 0.01s 15944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FHZaaK
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

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!