Facebook
From emanlaicepsa, 3 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 116
  1. #pragma GCC optimize("Ofast,unroll-loops")
  2. #pragma GCC target("avx,avx2,sse,sse2,sse3,fma")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define pb emplace_back
  9. #define all(n) (n).begin(),(n).end()
  10. #define mem(n,x) memset(n,x,sizeof(n))
  11. #define IOS ios::sync_with_stdio(0),cin.tie(0)
  12. #define pii pair<ll,ll>
  13. #define vi vector<ll>
  14. #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
  15. #define int ll
  16. template<typename A> void _do(A x){ cerr<<x<<"\n"; }
  17. template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}
  18.  
  19. ll n,m;
  20.  
  21. ll area(pii x, pii y){
  22.         if(x.fi > y.fi || x.se > y.se) return -100;
  23.         return (y.fi - x.fi) * (y.se - x.se);
  24. }
  25.  
  26. signed main(){
  27.         IOS;
  28.         cin>>n>>m;
  29.         deque<pii> sell(n), buy(m);
  30.         for(int i=0;i<n;i++){
  31.                 cin>>sell[i].fi>>sell[i].se;
  32.         }
  33.         for(int i=0;i<m;i++){
  34.                 cin>>buy[i].fi>>buy[i].se;
  35.         }
  36.  
  37.         sort(all(sell));
  38.         sort(all(buy));
  39.  
  40.         deque<pii> tmp;
  41.         for(auto i:sell){
  42.                 if(tmp.size() && i.se > tmp.back().se) continue;
  43.                 tmp.pb(i);
  44.         }
  45.         sell = tmp;
  46.         tmp.clear();
  47.         for(auto i:buy){
  48.                 while(tmp.size() && i.se > tmp.back().se) tmp.pop_back();
  49.                 tmp.pb(i);
  50.         }
  51.         buy = tmp;
  52.        
  53.         deque<pii> dq;
  54.         while(!sell.empty() && !buy.empty() && area(sell[0],buy[0]) <= 0){
  55.                 if(sell[0].fi >= buy[0].fi) buy.pop_front();
  56.                 else if(sell[0].se >= buy[0].se) sell.pop_front();
  57.                 else assert(false);
  58.         }
  59.         /* for(auto i:sell) cout<<i.fi<<" "<<i.se<<" "; cout<<'\n'; */
  60.         /* for(auto i:buy) cout<<i.fi<<" "<<i.se<<" "; cout<<'\n'; */
  61.         for(int i=0,siz=sell.size();i<siz;i++){
  62.                 while(dq.size()){
  63.                         auto &[pid,pl] = dq.back();
  64.                         if(area(sell[i],buy[pl]) <= area(sell[pid],buy[pl])) break;
  65.                         dq.pop_back();
  66.                 }
  67.                 if(dq.empty()){
  68.                         dq.pb(i,0);
  69.                 }
  70.                 else{
  71.                         int l = dq.back().se, r = buy.size(), pid = dq.back().fi;
  72.                         while(l<r){
  73.                                 int m = (l+r)/2;
  74.                                 ll cura = area(sell[i], buy[m]), prea = area(sell[pid], buy[m]);
  75.                                 /* dbg(m, cura, prea); */
  76.                                 if(cura < 0 && prea < 0){
  77.                                         if(buy[m].fi < sell[i].fi) l = m + 1;
  78.                                         else r = m;
  79.                                 }
  80.                                 else if(cura < 0 || prea >= cura) l = m + 1;
  81.                                 else r = m;
  82.                         }
  83.                         if(l < buy.size() && area(sell[i], buy[l]) > 0) dq.pb(i,l);
  84.                 }
  85.         }
  86.         /* for(auto i:dq) cout<<i.fi<<" "<<i.se<<'\n'; */
  87.         if(dq.empty()) return cout<<0<<'\n', 0;
  88.         ll ans = 0;
  89.         for(int i=0;i<buy.size();i++){
  90.                 while(dq.size() >= 2 && dq[1].se <= i) dq.pop_front();
  91.                 /* dbg(dq[0].fi, i); */
  92.                 ans = max(ans, area(sell[dq[0].fi], buy[i]));
  93.         }
  94.         cout<<ans<<'\n';
  95. }
  96.  
  97.