fork download
copy 
  1. //Author : Storm
  2. #include <bits/stdc++.h>
  3. #define freopen(file) if(fopen(file ".inp", "r")) { freopen(file ".INP", "r", stdin); freopen(file ".OUT", "w", stdout); }
  4. #define ll int
  5. #define se second
  6. #define fi first
  7. using namespace std;
  8. const int N = 3e5 + 5;
  9. ll n, x, y, v1, v2, suf[N], A[N], B[N];
  10. vector<pair<ll, ll> > a;
  11.  
  12. void input() {
  13.     cin >> x >> y >> n;
  14.     for(int i = 1; i <= n; i++) {
  15.         cin >> v1 >> v2;
  16.         a.push_back({v1, v2});
  17.     }
  18. }
  19. int cur = 0;
  20. vector<ll> mid;
  21. void pre(ll ymin, ll ymax, vector<pair<ll, ll> >& a) {
  22.     if(ymin >= ymax) {
  23.         return;
  24.     }
  25.     vector<pair<ll, ll> > b;
  26.     for(auto& p : a) {
  27.         if(p.se >= ymax || p.se <= ymin)continue;
  28.         b.push_back(p);
  29.     }
  30.     if(b.empty()) {
  31.         return;
  32.     }
  33.     ll ymid = (int) b.size();
  34.     if(ymid & 1)ymid /= 2;
  35.     else ymid = ymid / 2 - 1;
  36.     ymid = b[ymid].se;
  37.     mid.push_back(ymid);
  38.     vector<pair<ll, ll> > L, R;
  39.     for(auto& p : b) {
  40.         if(p.se <= ymid) {
  41.             L.push_back(p);
  42.         }
  43.         else {
  44.             R.push_back(p);
  45.         }
  46.     }
  47.     pre(ymin, ymid, L);
  48.     pre(ymid + 1, ymax, R);
  49. }
  50. ll calc(ll ymin, ll ymax, vector<pair<ll, ll> >& a) {
  51.     if(ymin >= ymax) {
  52.         return 0;
  53.     }
  54.     vector<pair<ll, ll> > b;
  55.     for(auto& p : a) {
  56.         if(p.se >= ymax || p.se <= ymin)continue;
  57.         b.push_back(p);
  58.     }
  59.     if(b.empty()) {
  60.         return 2 * (x + ymax - ymin);
  61.     }
  62.     vector<pair<ll, ll> > L, R;
  63.     for(int i = b.size() - 1; i >= 0; i--) {
  64.         if(b[i].fi <= x / 2) L.push_back(b[i]);
  65.     }
  66.     for(int i = 0; i < b.size(); i++) {
  67.         if(b[i].fi > x / 2) R.push_back(b[i]);
  68.     }
  69.     ll ymid = mid[cur++];
  70.     ll res = 0;
  71.     int m = L.size(), j = 0;
  72.     ll l = ymin, r = ymax;
  73.     vector<pair<ll, pair<ll, ll> > > c, d;
  74.     for(int i = j; i < m; i = j) {
  75.         c.push_back({L[i].fi, {l, r}});
  76.         while(j < m && L[j].fi == L[i].fi) {
  77.             if(L[j].se <= ymid) {
  78.                 l = max(l, L[j].se);
  79.             }
  80.             else {
  81.                 r = min(r, L[j].se);
  82.             }
  83.             j++;
  84.         }
  85.     }
  86.     c.push_back({0, {l, r}});
  87.     m = R.size(), j = 0;
  88.     l = ymin, r = ymax;
  89.     for(int i = j; i < m; i = j) {
  90.         d.push_back({R[i].fi, {l, r}});
  91.         while(j < m && R[j].fi == R[i].fi) {
  92.             if(R[j].se <= ymid) {
  93.                 l = max(l, R[j].se);
  94.             }
  95.             else {
  96.                 r = min(r, R[j].se);
  97.             }
  98.             j++;
  99.         }
  100.     }
  101.     d.push_back({x, {l, r}});
  102.     m = d.size();
  103.     suf[m - 1] = d[m - 1].fi + d[m - 1].se.se - d[m - 1].se.fi;
  104.     for(int i = m - 2; i >= 0; i--) {
  105.         suf[i] = max(suf[i + 1], d[i].fi + d[i].se.se - d[i].se.fi);
  106.     }
  107.     for(int i = 0; i < m; i++) {
  108.         A[i] = d[i].fi - d[i].se.fi;
  109.         B[i] = d[i].fi + d[i].se.se;
  110.     }
  111.     int j1 = 0, j2 = 0;
  112.     deque<int> dA, dB;
  113.     int jA = 0, jB = 0;
  114.     for(auto& cur : c) {
  115.         while(j1 < m && d[j1].se.fi <= cur.se.fi)j1++;
  116.         while(j2 < m && d[j2].se.se >= cur.se.se)j2++;
  117.         while(jA < j2) {
  118.             while(!dA.empty() && A[dA.back()] <= A[jA])dA.pop_back();
  119.             dA.push_back(jA);
  120.             jA++;
  121.         }
  122.         while(!dA.empty() && dA.front() < j1)dA.pop_front();
  123.         while(jB < j1) {
  124.             while(!dB.empty() && B[dB.back()] <= B[jB])dB.pop_back();
  125.             dB.push_back(jB);
  126.             jB++;
  127.         }
  128.         while(!dB.empty() && dB.front() < j2)dB.pop_front();
  129.         int k = max(j1, j2);
  130.         if(k < m) {
  131.             res = max(res, 2 * (suf[k] - cur.fi));
  132.         }
  133.         k = min(j1 - 1, j2 - 1);
  134.         if(k >= 0) {
  135.             res = max(res, 2 * (d[k].fi - cur.fi + cur.se.se - cur.se.fi));
  136.         }
  137.         if(!dA.empty()) {
  138.             res = max(res, 2 * (cur.se.se - cur.fi + A[dA.front()]));
  139.         }
  140.         if(!dB.empty()) {
  141.             res = max(res, 2 * (-cur.se.fi - cur.fi + B[dB.front()]));
  142.         }
  143.     }
  144.     L.clear();
  145.     R.clear();
  146.     for(auto& p : b) {
  147.         if(p.se <= ymid) {
  148.             L.push_back(p);
  149.         }
  150.         else {
  151.             R.push_back(p);
  152.         }
  153.     }
  154.     res = max({res, calc(ymin, ymid, L), calc(ymid + 1, ymax, R)});
  155.     return res;
  156. }
  157. void solve() {
  158.     sort(a.begin(), a.end(), [&] (pair<ll, ll> x, pair<ll, ll> y) {
  159.         return x.se < y.se;
  160.     });
  161.     pre(0, y, a);
  162.     sort(a.begin(), a.end(), [&] (pair<ll, ll> x, pair<ll, ll> y) {
  163.         return x.fi < y.fi;
  164.     });
  165.     ll res = calc(0, y, a);
  166.     swap(x, y);
  167.     for(auto& p : a) {
  168.         swap(p.fi, p.se);
  169.     }
  170.     sort(a.begin(), a.end(), [&] (pair<ll, ll> x, pair<ll, ll> y) {
  171.         return x.se < y.se;
  172.     });
  173.     cur = 0;
  174.     mid.clear();
  175.     pre(0, y, a);
  176.     sort(a.begin(), a.end(), [&] (pair<ll, ll> x, pair<ll, ll> y) {
  177.         return x.fi < y.fi;
  178.     });
  179.     res = max(res, calc(0, y, a));
  180.     cout << res;
  181. }
  182.  
  183. /*
  184.  
  185. */
  186.  
  187. int main() {
  188.     ios_base::sync_with_stdio(0);
  189.     cin.tie(0);cout.tie(0);
  190.     freopen("HALFFILL");
  191.     int t = 1;
  192.     while(t--) {
  193.         input();
  194.         solve();
  195.     }
  196.     return 0;
  197. }
  198.  
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nXtB9b
language:
C++ (gcc 8.3)
created:
15 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!