fork download
copy 
  1. // TrungNotChung
  2. #include <bits/stdc++.h>
  3. #define pii pair<int, int>
  4. #define fi first
  5. #define se second
  6. #define BIT(x, i) (1 & ((x) >> (i)))
  7. #define MASK(x) (1LL << (x))
  8. #define CNT(x) __builtin_popcountll(x)
  9. #define task "area"
  10.  
  11. using namespace std;
  12. const int N = (int)2e5 + 228;
  13. const int INF =  (int)1e9 + 7;
  14.  
  15. struct Point {
  16.     int x, y;
  17. };
  18.  
  19. struct Segment {
  20.     Point p1, p2;
  21. };
  22.  
  23. struct Event {
  24.     int x, l, r, tp, id;
  25.     Event(int _x = 0, int _l = 0, int _r = 0, int _tp = 0) {
  26.         x = _x, l = _l, r = _r, tp = _tp;
  27.     }
  28.     bool operator < (const Event& other) const {
  29.         return (x == other.x ? tp < other.tp : x < other.x);
  30.     }
  31. }e[N];
  32.  
  33. int len[N];
  34.  
  35. namespace Area {
  36.     struct SegmentTree {
  37.         vector<int> cnt;
  38.         vector<int> sum;
  39.         int n;
  40.  
  41.         SegmentTree(int _n = 0) {
  42.             n = _n;
  43.             cnt.assign(4 * n + 7, 0);
  44.             sum.assign(4 * n + 7, 0);
  45.         }
  46.  
  47.         void update(int id, int l, int r, int u, int v, int tp) {
  48.             if(l > v || r < u) {
  49.                 return;
  50.             }
  51.             if(u <= l && r <= v) {
  52.                 cnt[id] += tp;
  53.                 if(cnt[id] == 0) {
  54.                     if(l != r) {
  55.                         sum[id] = sum[id * 2] + sum[id * 2 + 1];
  56.                     } else {
  57.                         sum[id] = 0;
  58.                     }
  59.                 } else {
  60.                     sum[id] = len[r] - (l == 0 ? 0 : len[l-1]);
  61.                 }
  62.                 // cout << l << " " << r << " " << sum[id] << "\n";
  63.                 return;
  64.             }
  65.             int mid = (l + r) / 2;
  66.             update(id * 2, l, mid, u, v, tp);
  67.             update(id * 2 + 1, mid + 1, r, u, v, tp);
  68.             if(cnt[id] == 0) {
  69.                 sum[id] = sum[id * 2] + sum[id * 2 + 1];
  70.             } else {
  71.                 sum[id] = len[r] - (l == 0 ? 0 : len[l-1]);
  72.             }
  73.         }
  74.     };
  75.  
  76.     long long calc(vector<Segment> candidates) {
  77.         vector<int> py;
  78.         int m = 0;
  79.         for(int i = 0; i < (int)candidates.size(); ++i) {
  80.             py.push_back(candidates[i].p1.y);
  81.             py.push_back(candidates[i].p2.y + 1);
  82.             e[++m] = Event(candidates[i].p1.x, candidates[i].p1.y, candidates[i].p2.y, 1);
  83.             e[++m] = Event(candidates[i].p2.x + 1, candidates[i].p1.y, candidates[i].p2.y, -1);
  84.         }
  85.  
  86.         py.push_back(-INF);
  87.         sort(py.begin(), py.end());
  88.         py.erase(unique(py.begin(), py.end()), py.end());
  89.         int sz = (int)py.size() - 1;
  90.         for(int i = 1; i < sz; ++i) {
  91.             len[i] = len[i-1] + py[i+1] - py[i];
  92.         }
  93.         SegmentTree it = SegmentTree(sz);
  94.  
  95.         sort(e + 1, e + m + 1);
  96.         long long ans = 0;
  97.         for(int i = 1; i <= m; ++i) {
  98.             if(i > 1) {
  99.                 ans += 1LL * (e[i].x - e[i-1].x) * it.sum[1];
  100.             }
  101.             // cout << it.sum[1] << "\n";
  102.             int l = lower_bound(py.begin(), py.end(), e[i].l) - py.begin();
  103.             int r = lower_bound(py.begin(), py.end(), e[i].r + 1) - py.begin() - 1;
  104.             // cout << e[i].x << " " << l << " " << r << " " << len[r] - len[l-1] << " " << e[i].tp << "\n";
  105.             it.update(1, 1, sz, l, r, e[i].tp);
  106.         }
  107.         return ans;
  108.     }
  109. }
  110.  
  111. namespace Component {
  112.     bool isEnd[N];
  113.     int endTime[N];
  114.  
  115.     struct DisjointSet
  116.     {
  117.         vector<int> lab;
  118.         int n;
  119.         DisjointSet(int _n = 0)
  120.         {
  121.             n = _n;
  122.             lab.assign(n+7, -1);
  123.         }
  124.         int Find(int u)
  125.         {
  126.             if(lab[u] < 0)
  127.                 return u;
  128.             return lab[u] = Find(lab[u]);
  129.         }
  130.         bool join(int u, int v)
  131.         {
  132.             u = Find(u), v = Find(v);
  133.             if(u == v)
  134.                 return false;
  135.             if(lab[u] < lab[v]) 
  136.                 swap(u, v);
  137.             lab[v] += lab[u], lab[u] = v;
  138.             return true;
  139.         }
  140.     }dsu;
  141.  
  142.     struct SegmentTree
  143.     {
  144.         vector<int> cnt;
  145.         vector<vector<int> > node1, node2;
  146.         int n;
  147.         SegmentTree(int _n = 0)
  148.         {
  149.             n = _n;
  150.             cnt.assign(4 * n + 7, 0);
  151.             node1.assign(4 * n + 7, vector<int>());
  152.             node2.assign(4 * n + 7, vector<int>());
  153.         }
  154.  
  155.         void join(vector<int> &a, int node) {
  156.             int best = -1;
  157.             for(int x : a) {
  158.                 if(isEnd[x]) {
  159.                     continue;
  160.                 }
  161.                 // cout << "Join: " << node << " " << x << '\n';
  162.                 if(best == -1 || endTime[x] > endTime[best]) {
  163.                     best = x;
  164.                 }
  165.                 dsu.join(x, node);
  166.             }
  167.             a.clear();
  168.             if(best != -1) {
  169.                 a.push_back(best);
  170.             }
  171.         }
  172.  
  173.         void update(int id, int l, int r, int u, int v, int node)
  174.         {
  175.             if(l > v || r < u) {
  176.                 return;
  177.             }
  178.             join(node1[id], node);
  179.  
  180.             if(u <= l && r <= v) {
  181.                 // node2[id].push_back(node);
  182.                 // node1[id].push_back(node);
  183.                 join(node2[id], node);
  184.                 return;
  185.             }
  186.             // node2[id].push_back(node);
  187.             int mid = (l + r) / 2;
  188.             update(id * 2, l, mid, u, v, node);
  189.             update(id * 2 + 1, mid + 1, r, u, v, node);
  190.         }
  191.  
  192.         void add(int id, int l, int r, int u, int v, int node)
  193.         {
  194.             if(l > v || r < u) {
  195.                 return;
  196.             }
  197.  
  198.             if(u <= l && r <= v) {
  199.                 node2[id].push_back(node);
  200.                 node1[id].push_back(node);
  201.                 return;
  202.             }
  203.             node2[id].push_back(node);
  204.  
  205.             int mid = (l + r) / 2;
  206.             add(id * 2, l, mid, u, v, node);
  207.             add(id * 2 + 1, mid + 1, r, u, v, node);
  208.         }
  209.     };
  210.  
  211.     vector<int> calc(vector<Segment> candidates) {
  212.         int n = (int)candidates.size();
  213.         vector<int> py;
  214.         int m = 0;
  215.         for(int i = 0; i < (int)candidates.size(); ++i) {
  216.             py.push_back(candidates[i].p1.y-1);
  217.             py.push_back(candidates[i].p1.y);
  218.             py.push_back(candidates[i].p2.y);
  219.             py.push_back(candidates[i].p2.y + 1);
  220.             e[++m] = Event(candidates[i].p1.x, candidates[i].p1.y - 1, candidates[i].p2.y + 1, 1);
  221.             e[m].id = i + 1;
  222.             endTime[i+1] = candidates[i].p2.x;
  223.             e[++m] = Event(candidates[i].p2.x + 1, candidates[i].p1.y, candidates[i].p2.y, -1);
  224.             e[m].id = i + 1 + n;
  225.             endTime[i+1+n] = candidates[i].p2.x + 1;
  226.         }
  227.  
  228.         dsu = DisjointSet(n * 2);
  229.         for(int i = 1; i <= n; ++i) {
  230.             dsu.join(i, i + n);
  231.         }
  232.         py.push_back(-INF);
  233.         sort(py.begin(), py.end());
  234.         py.erase(unique(py.begin(), py.end()), py.end());
  235.         int sz = (int)py.size();
  236.         SegmentTree it = SegmentTree(sz);
  237.  
  238.         sort(e + 1, e + m + 1);
  239.         priority_queue<pii, vector<pii>, greater<pii> > pq;
  240.         for(int i = 1; i <= m; ++i) {
  241.             while(pq.size() && pq.top().fi < e[i].x) {
  242.                 int id = pq.top().se;
  243.                 // cout << i << " " << id << '\n';
  244.                 pq.pop();
  245.                 isEnd[id] = true;
  246.             }
  247.             int id = e[i].id;
  248.             int l = lower_bound(py.begin(), py.end(), e[i].l) - py.begin();
  249.             int r = lower_bound(py.begin(), py.end(), e[i].r) - py.begin();
  250.             // cout << e[i].x << " " << id << " " << l << " " << r << '\n';
  251.             if(id <= n) {
  252.                 int x = lower_bound(py.begin(), py.end(), e[i].l + 1) - py.begin();
  253.                 int y = lower_bound(py.begin(), py.end(), e[i].r - 1) - py.begin();
  254.                 // cout << x << " " << y << '\n';
  255.                 it.update(1, 1, sz, x, y, id);
  256.             }
  257.             // cout << "Add:\n";
  258.             it.add(1, 1, sz, l, r, id);
  259.             pq.push({endTime[id], id});
  260.         }
  261.  
  262.         vector<int> ans;
  263.         for(int i = 1; i <= n; ++i) {
  264.             ans.push_back(dsu.Find(i));
  265.         }
  266.         return ans;
  267.     }
  268. }
  269.  
  270. int n;
  271. Segment segs[N];
  272.  
  273. void solve() {
  274.     cin >> n;
  275.     for(int i = 1; i <= n; ++i) {
  276.         int x, y, u, v;
  277.         cin >> x >> y >> u >> v;
  278.         segs[i].p1 = {x, y};
  279.         segs[i].p2 = {u, v};
  280.     }
  281.  
  282.     vector<Segment> candidates;
  283.     for(int i = 1; i <= n; ++i) {
  284.         if(segs[i].p1.x > segs[i].p2.x) {
  285.             continue;
  286.         }
  287.         if(segs[i].p1.y > segs[i].p2.y) {
  288.             continue;
  289.         }
  290.         candidates.push_back(segs[i]);
  291.     }
  292.  
  293.     vector<int> comp = Component::calc(candidates);
  294.     // for(int x : comp) {
  295.     //     cout << x << " ";
  296.     // }
  297.     // cout << '\n';
  298.     vector<int> perm;
  299.     for(int i = 1; i <= n; ++i) {
  300.         perm.push_back(i);
  301.     }
  302.     sort(perm.begin(), perm.end(), [&](int u, int v) {
  303.         return comp[u-1] < comp[v-1];
  304.     });
  305.  
  306.     long long ans = 0;
  307.     int cur = 0;
  308.     while(cur < n) {
  309.         int nxt = cur;
  310.         while(nxt < n && comp[perm[nxt] - 1] == comp[perm[cur] - 1]) {
  311.             ++nxt;
  312.         }
  313.         vector<Segment> tmp;
  314.         for(int i = cur; i < nxt; ++i) {
  315.             tmp.push_back(segs[perm[i]]);
  316.         }
  317.         ans = max(ans, Area::calc(tmp));
  318.         cur = nxt;
  319.     }
  320.  
  321.     cout << ans;
  322. }
  323.  
  324. int main()
  325. {
  326.     ios_base::sync_with_stdio(false);
  327.     cin.tie(0);
  328.     cout.tie(0);
  329.     freopen(task ".inp", "r", stdin);
  330.     freopen(task ".out", "w", stdout);
  331.     solve();
  332.     // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  333.     return 0;
  334. }
  335.  
Success #stdin #stdout 0.01s 11088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gQqTdN
language:
C++14 (gcc 8.3)
created:
1 year 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!