fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define F first
  5. #define S second
  6. #define pb push_back
  7. #define vll vector<ll>
  8. #define pll pair<ll, ll>
  9.  
  10. typedef int ll;
  11.  
  12. const ll mxN=5e4+5;
  13. const ll LOG=21;
  14.  
  15. ll dsu[mxN];
  16. ll ans[mxN];
  17. ll svid[mxN][LOG];
  18.  
  19. ll find_set(ll tar){
  20.     if(dsu[tar]<0) return tar;
  21.     return dsu[tar]=find_set(dsu[tar]);
  22. }
  23.  
  24. void unite(ll a, ll b){
  25.     ll f=find_set(a);
  26.     ll s=find_set(b);
  27.     assert(f!=s);
  28.     if(abs(dsu[f])<abs(dsu[s])) swap(f, s);
  29.     dsu[f]+=dsu[s];
  30.     ans[f] += ans[s];
  31.     dsu[s]=f;
  32. }
  33.  
  34. struct segtree1{
  35.     vector<pll> tree;
  36.     ll treelen;
  37.  
  38.     void init(ll siz){
  39.         treelen=siz+1;
  40.         while(__builtin_popcount(treelen)!=1) treelen++;
  41.         tree=vector<pll> (2*treelen, make_pair(0, 0));
  42.     }
  43.  
  44.     void add1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll id){
  45.         if(low>=qlow && high<=qhigh){
  46.             if(tree[idx].S!=0){
  47.                 if(find_set(tree[idx].F)!=find_set(id)){
  48.                     unite(tree[idx].F, id);
  49.                 }
  50.             }
  51.             tree[idx].F=id;
  52.             tree[idx].S++;
  53.             return;
  54.         }
  55.         if(low>qhigh || high<qlow){
  56.             return;
  57.         }
  58.         ll mid=(low+high)/2;
  59.         add1(2*idx, low, mid, qlow, qhigh, id);
  60.         add1(2*idx+1, mid+1, high, qlow, qhigh, id);
  61.     }
  62.  
  63.     void add(ll qlow, ll qhigh, ll id){
  64.         add1(1, 0, treelen-1, qlow, qhigh, id);
  65.     }
  66.  
  67.     void rem1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll id){
  68.         if(low>=qlow && high<=qhigh){
  69.             tree[idx].S--;
  70.             return;
  71.         }
  72.         if(low>qhigh || high<qlow){
  73.             return;
  74.         }
  75.         ll mid=(low+high)/2;
  76.         rem1(2*idx, low, mid, qlow, qhigh, id);
  77.         rem1(2*idx+1, mid+1, high, qlow, qhigh, id);
  78.     }
  79.  
  80.     void rem(ll qlow, ll qhigh, ll id){
  81.         rem1(1, 0, treelen-1, qlow, qhigh, id);
  82.     }
  83.  
  84.     void qry(ll idx, ll id){
  85.         ll tar=idx+treelen;
  86.         while(tar>0){
  87.             if(tree[tar].S>0){
  88.                 if(find_set(tree[tar].F)!=find_set(id)){
  89.                     unite(tree[tar].F, id);
  90.                 }
  91.             }
  92.             tar/=2;
  93.         }
  94.     }
  95. };
  96.  
  97. struct segtree2{
  98.     vector<vector<pll>> tree;
  99.     ll treelen;
  100.     ll d;
  101.  
  102.     void init(ll siz){
  103.         treelen=siz+1;
  104.         while(__builtin_popcount(treelen)!=1) treelen++;
  105.         d=__builtin_ctz(treelen);
  106.         tree=vector<vector<pll>> (2*treelen, vector<pll>());
  107.     }
  108.  
  109.     void add(ll idx, ll id){
  110.         // cout<<"adding "<<idx<<' '<<id<<'\n';
  111.         ll tar=idx+treelen;
  112.         ll dep=d;
  113.         while(tar>0){
  114.             svid[id][dep]=(ll) tree[tar].size();
  115.             // cout<<"dep: "<<dep<<'\n';
  116.             // cout<<"svid["<<id<<"]["<<dep<<"] : "<<svid[id][dep]<<'\n'; 
  117.             tree[tar].pb({id, 1});
  118.             tar/=2;
  119.             dep--;
  120.         }
  121.         assert(dep==-1);
  122.     }
  123.  
  124.     void rem(ll idx, ll id){
  125.         ll tar=idx+treelen;
  126.         ll dep=d;
  127.         while(tar>0){
  128.             assert(svid[id][dep]<tree[tar].size());
  129.             // cout<<"svid["<<id<<"]["<<dep<<"] : "<<svid[id][dep]<<'\n';
  130.             tree[tar][svid[id][dep]].S--;
  131.             tar/=2;
  132.             dep--;
  133.         }
  134.         assert(dep==-1);
  135.     }
  136.  
  137.     void qry1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll id, ll dep){
  138.         if(low>=qlow && high<=qhigh){
  139.             ll siz=0;
  140.             ll dumb=0;
  141.             for(auto &[x, y]:tree[idx]){
  142.                 if(y>0){
  143.                     dumb=x;
  144.                     svid[x][dep]=0;
  145.                     // cout<<"svid["<<x<<"]["<<dep<<"] : "<<svid[id][dep]<<'\n';
  146.                     if(find_set(x)!=find_set(id)){
  147.                         unite(x, id);
  148.                     }
  149.                 }
  150.                 siz+=y;
  151.             }
  152.             tree[idx].clear();
  153.             if(siz>0) tree[idx].pb({dumb, siz});
  154.             // svid[id][dep]=0;
  155.             // cout<<"svid["<<id<<"]["<<dep<<"] : "<<svid[id][dep]<<'\n';
  156.             return;
  157.         }
  158.         if(low>qhigh || high<qlow){
  159.             return;
  160.         }
  161.         ll mid=(low+high)/2;
  162.         qry1(2*idx, low, mid, qlow, qhigh, id, dep+1);
  163.         qry1(2*idx+1, mid+1, high, qlow, qhigh, id, dep+1);
  164.     }
  165.  
  166.     void qry(ll qlow, ll qhigh, ll id){
  167.         qry1(1, 0, treelen-1, qlow, qhigh, id, 0);
  168.     }
  169. };
  170.  
  171. ll n;
  172. vll con;
  173. segtree1 seg1;
  174. segtree2 seg2;
  175. vector<array<ll, 3>> v;
  176. ll siz;
  177.  
  178. ll id(ll tar){
  179.     return lower_bound(con.begin(), con.end(), tar)-con.begin();
  180. }
  181.  
  182. bool compare(array<ll, 3> a, array<ll, 3> b){
  183.     if(a[0]!=b[0]){
  184.         return a[0]<b[0];
  185.     }
  186.     if(a[1]!=b[1]){
  187.         return a[1]>b[1];
  188.     }
  189.     return a[2]<b[2];
  190. }
  191.  
  192. int solve(int N){
  193.     memset(dsu, -1, sizeof(dsu));
  194.     for(int i = 0; i < mxN; i++){
  195.         ans[i] = 0;
  196.     }
  197.     memset(svid, 0, sizeof(svid));
  198.     n=N;
  199.     vector<int>a(n), b(n), c(n), d(n);
  200.     for(ll i=0;i<n;i++){
  201.         int x, y, h, w;
  202.         cin >> x >> y >> h >> w;
  203.         a[i] = x;
  204.         c[i] = x + h;
  205.         b[i] = y;
  206.         d[i] = y + w;
  207.         con.pb(b[i]);
  208.         con.pb(d[i]);
  209.         v.pb({a[i], 1, i});
  210.         v.pb({c[i], -1, i});
  211.         ans[i] = h * w;
  212.     }
  213.     sort(con.begin(), con.end());
  214.     con.erase(unique(con.begin(), con.end()), con.end());
  215.     sort(v.begin(), v.end(), compare);
  216.     siz=(ll) con.size();
  217.     seg1.init(siz);
  218.     seg2.init(siz);
  219.     for(auto &it:v){
  220.         ll cur=it[2];
  221.         if(it[1]==1){
  222.             seg1.qry(id(b[cur]), cur);
  223.             seg1.qry(id(d[cur]), cur);
  224.             seg2.qry(id(b[cur]), id(d[cur]), cur);
  225.             seg1.add(id(b[cur]), id(d[cur]), cur);
  226.             seg2.add(id(b[cur]), cur);
  227.             // seg2.add(id(d[cur]), cur);
  228.         }
  229.         else{
  230.             assert(it[1]==-1);
  231.             seg1.rem(id(b[cur]), id(d[cur]), cur);
  232.             seg2.rem(id(b[cur]), cur);
  233.             // seg2.rem(id(d[cur]), cur);
  234.         }
  235.     }
  236.     con.clear();
  237.     for(ll i=0;i<n;i++){
  238.         con.pb(find_set(i));
  239.     }
  240.     sort(con.begin(), con.end());
  241.     con.erase(unique(con.begin(), con.end()), con.end());
  242.     vll re(n);
  243.     int an = 0;
  244.     for(ll i=0;i<n;i++){
  245.         an = max(an, ans[find_set(i)]);
  246.     }
  247.     return an;
  248. }
  249. int main(){
  250.     int n;
  251.     while(cin >> n){
  252.         cout << solve(n) << '\n';
  253.     }
  254. }
Success #stdin #stdout 0.01s 8036KB
comments ()
stdin
copy 
8
14 1 2 2
16 9 1 5
11 3 5 2
3 4 2 5
5 9 3 2
21 3 2 8
13 2 1 1
13 8 3 5
stdout
copy 
20
https://ideone.com/vZEmio
language:
C++14 (gcc 8.3)
created:
5 days 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!