fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7.  
  8. struct edge
  9. {
  10.     int v, to, cap, scap;
  11.     edge(int a, int b, int c)
  12.     {
  13.         v = a, to = b, cap = c, scap = c;
  14.     }
  15.     edge() {}
  16. };
  17.  
  18. struct rect
  19. {
  20.     int x1, y1, x2, y2;
  21. };
  22.  
  23. struct tri
  24. {
  25.     int y1, y2, x;
  26. };
  27.  
  28. bool operator < (const tri &a, const tri &b)
  29. {
  30.     return a.y1 < b.y1;
  31. };
  32.  
  33. const int N = 1e6 + 7;
  34. const int INF = 1e9 + 7;
  35.  
  36. vector <edge> e;
  37. vector <int> g[N];
  38. int us[N];
  39. int usbs = 1;
  40. int d[N];
  41. int q[N];
  42. int ded[N];
  43. int ptr[N];
  44. vector <rect> fget[N];
  45. int after_bfs = 1;
  46. int visb = 1;
  47. ll ans = 0;
  48. int qh, qt;
  49. int s, t;
  50. int l;
  51.  
  52. bool bfs()
  53. {
  54.     qh = qt = 0;
  55.     us[s] = usbs;
  56.     q[qt++] = s;
  57.     d[s] = 0;
  58.     while (qh < qt)
  59.     {
  60.         int v = q[qh++];
  61.         for (auto c : g[v])
  62.         {
  63.             if (us[e[c].to] != usbs && e[c].cap > 0)
  64.             {
  65.                 d[e[c].to] = d[v] + 1;
  66.                 us[e[c].to] = usbs;
  67.                 q[qt++] = e[c].to;
  68.             }
  69.         }
  70.     }
  71.     return (us[t] == usbs++);
  72. }
  73.  
  74. int dfs(int v = s, int c = 1e9)
  75. {
  76.     if (!c)
  77.     {
  78.         return 0;
  79.     }
  80.     if (v == t)
  81.     {
  82.         ans += c;
  83.         return c;
  84.     }
  85.     if (ded[v] != after_bfs)
  86.     {
  87.         ded[v] = after_bfs;
  88.         ptr[v] = 0;
  89.     }
  90.     for (; ptr[v] < (int) g[v].size(); ptr[v]++)
  91.     {
  92.         int ind = g[v][ptr[v]];
  93.         if (e[ind].cap > 0 && d[e[ind].to] == d[v] + 1)
  94.         {
  95.             int x = dfs(e[ind].to, min(c, e[ind].cap));
  96.             if (x)
  97.             {
  98.                 e[ind].cap -= x;
  99.                 e[ind ^ 1].cap += x;
  100.                 return x;
  101.             }
  102.         }
  103.     }
  104.     return 0;
  105. }
  106.  
  107. void add_edge(int u, int v, int cap)
  108. {
  109.     g[u].push_back(e.size());
  110.     e.push_back({u, v, cap});
  111.     g[v].push_back(e.size());
  112.     e.push_back({v, u, 0});
  113. }
  114.  
  115. ll dinic(int a, int b)
  116. {
  117.     s = a, t = b;
  118.     while (bfs())
  119.     {
  120.         after_bfs++;
  121.         while (dfs())
  122.         {
  123.             continue;
  124.         }
  125.     }
  126.     return ans;
  127. }
  128.  
  129. vector <int> inds;
  130.  
  131. int lel(int v, int l, int r, int i)
  132. {
  133.     if (r - l == 1)
  134.     {
  135.         return v;
  136.     }
  137.     else
  138.     {
  139.         int m = (l + r) / 2;
  140.         if (i < m)
  141.         {
  142.             return lel(v * 2 + 1, l, m, i);
  143.         }
  144.         else
  145.         {
  146.             return lel(v * 2 + 2, m, r, i);
  147.         }
  148.     }
  149. }
  150.  
  151. void get(int v, int l, int r, int tl, int tr)
  152. {
  153.     if (tl >= r || tr <= l)
  154.     {
  155.         return;
  156.     }
  157.     if (tl >= l && tr <= r)
  158.     {
  159.         inds.push_back(v);
  160.     }
  161.     else
  162.     {
  163.         int tm = (tl + tr) / 2;
  164.         get(v * 2 + 1, l, r, tl, tm);
  165.         get(v * 2 + 2, l, r, tm, tr);
  166.     }
  167. }
  168.  
  169. void build(int v, int l, int r, int ax, int bx, int n)
  170. {
  171.     if (r - l == 1)
  172.     {
  173.         add_edge(l, ax + v, 1);
  174.         add_edge(bx + v, n + l, 1);
  175.     }
  176.     else
  177.     {
  178.         int m = (l + r) / 2;
  179.         build(v * 2 + 1, l, m, ax, bx, n);
  180.         build(v * 2 + 2, m, r, ax, bx, n);
  181.         add_edge(ax + v * 2 + 1, ax + v, INF);
  182.         add_edge(ax + v * 2 + 2, ax + v, INF);
  183.         add_edge(bx + v, bx + v * 2 + 1, INF);
  184.         add_edge(bx + v, bx + v * 2 + 2, INF);
  185.     }
  186. }
  187.  
  188. int main()
  189. {
  190. #ifdef ONPC
  191.     freopen("a.in", "r", stdin);
  192.     //freopen("a.out", "w", stdout);
  193. #else
  194.     //freopen("a.in", "r", stdin);
  195.     //freopen("a.out", "w", stdout);
  196. #endif
  197.     vector <rect> fre;
  198.     int n, q;
  199.     scanf("%d", &n);
  200.     scanf("%d", &q);
  201.     for (int i = 0; i < q; i++)
  202.     {
  203.         int x1, y1, x2, y2;
  204.         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  205.         x1--, y1--, x2--, y2--;
  206.         fget[x2].push_back({x1, y1, x2, y2});
  207.     }
  208.     set <tri> s;
  209.     s.insert({0, n - 1, 0});
  210.     for (int i = 0; i < n; i++)
  211.     {
  212.         for (auto c : fget[i])
  213.         {
  214.             auto it = s.lower_bound({c.y1, -1, -1});
  215.             vector <tri> gt;
  216.             if (it != s.begin())
  217.             {
  218.                 it--;
  219.                 gt.push_back(*it);
  220.                 it++;
  221.             }
  222.             bool b = false;
  223.             while (it != s.end() && (it->y2 <= c.y2 || !b))
  224.             {
  225.                 gt.push_back(*it);
  226.                 it++;
  227.                 if (it != s.end())
  228.                 {
  229.                     if (it->y2 > c.y2)
  230.                     {
  231.                         gt.push_back(*it);
  232.                         b = true;
  233.                     }
  234.                 }
  235.             }
  236.             for (auto d : gt)
  237.             {
  238.                 if (max(d.y1, c.y1) > min(d.y2, c.y2))
  239.                 {
  240.                     continue;
  241.                 }
  242.                 s.erase(d);
  243.                 if (c.y1 <= d.y1 && d.y2 <= c.y2)
  244.                 {
  245.                     int a = d.x, b = c.x1 - 1;
  246.                     if (a <= b)
  247.                     {
  248.                         fre.push_back({a, d.y1, b, d.y2});
  249.                     }
  250.                 }
  251.                 else
  252.                 {
  253.                     if (d.y1 <= c.y1 && c.y2 <= d.y2)
  254.                     {
  255.                         auto was = d;
  256.                         was.y2 = c.y1 - 1;
  257.                         if (was.y1 <= was.y2)
  258.                         {
  259.                             s.insert(was);
  260.                         }
  261.                         was = d;
  262.                         was.y1 = c.y2 + 1;
  263.                         if (was.y1 <= was.y2)
  264.                         {
  265.                             s.insert(was);
  266.                         }
  267.                         int a = d.x, b = c.x1 - 1;
  268.                         if (a <= b)
  269.                         {
  270.                             fre.push_back({a, c.y1, b, c.y2});
  271.                         }
  272.                     }
  273.                     else if (d.y2 > c.y2)
  274.                     {
  275.                         auto was = d;
  276.                         was.y1 = c.y2 + 1;
  277.                         s.insert(was);
  278.                         int a = d.x, b = c.x1 - 1;
  279.                         if (a <= b)
  280.                         {
  281.                             fre.push_back({a, d.y1, b, c.y2});
  282.                         }
  283.                     }
  284.                     else if (d.y1 < c.y1)
  285.                     {
  286.                         auto was = d;
  287.                         was.y2 = c.y1 - 1;
  288.                         s.insert(was);
  289.                         int a = d.x, b = c.x1 - 1;
  290.                         if (a <= b)
  291.                         {
  292.                             fre.push_back({a, c.y1, b, d.y2});
  293.                         }
  294.                     }
  295.                 }
  296.             }
  297.             if (c.x2 != n - 1)
  298.             {
  299.                 s.insert({c.y1, c.y2, c.x2 + 1});
  300.             }
  301.         }
  302.     }
  303.     for (auto c : s)
  304.     {
  305.         fre.push_back({c.x, c.y1, n - 1, c.y2});
  306.     }
  307.     inds.clear();
  308.     get(0, n - 1, n, 0, n);
  309.     int cnt = inds[0] + 1;
  310.     for (auto c : fre)
  311.     {
  312.         int x1 = c.x1, y1 = c.y1, x2 = c.x2, y2 = c.y2;        
  313.         inds.clear();
  314.         get(0, x1, x2 + 1, 0, n);
  315.         vector <int> a = inds;
  316.         inds.clear();
  317.         get(0, y1, y2 + 1, 0, n);
  318.         vector <int> b = inds;
  319.         for (auto c : a)
  320.         {
  321.             for (auto d : b)
  322.             {
  323.                 add_edge(n + n + c, n + n + cnt + d, INF);
  324.             }
  325.         }
  326.     }
  327.     build(0, 0, n, n + n, n + n + cnt, n);
  328.     int st = n + n + cnt + cnt, en = n + n + cnt + cnt + 1;
  329.     for (int i = 0; i < n; i++)
  330.     {
  331.         add_edge(st, i, 1);
  332.         add_edge(i + n, en, 1);
  333.     }
  334.     printf("%lld\n", dinic(st, en));
  335. }
  336.  
Runtime error #stdin #stdout 0.01s 82496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wHieAz
language:
C++14 (gcc 8.3)
created:
7 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!