#include <iostream>
#include<vector>
using namespace std;
class Solution
{
public:
void sortInPlace(vector<int>& v)
{
int len = v.size();
for(int i =0; i <len ; i++)
{
int k = i;
while(k>0)
{
int par = (k-1)/2;
if(v[k] > v[par])
{
swap(v[k],v[par]);
k = par;
}
else break;
}
}
for(int j=len-1 ; j>0 ; j--)
{
swap(v[0],v[j]);
int k = 0;
while(2*k+1 < j)
{
int left = 2*k +1 ;
int right = 2*k +2 ;
int largest = left;
if(right < j && v[right] > v[largest])
largest = right;
if(v[largest] > v[k])
{
swap(v[k],v[largest]);
k = largest;
}
else break;
}
}
}
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts)
{
sortInPlace(verticalCuts);
sortInPlace(horizontalCuts);
long long vert = verticalCuts.front(),horz = horizontalCuts.front();
int max = 1;
for(vector<int>::iterator i = verticalCuts.begin();i!= verticalCuts.end()-1;i++)
if( *(i+1) - *i > vert)
vert = *(i+1) - *i;
for(vector<int>::iterator i = horizontalCuts.begin();i!= horizontalCuts.end()-1;i++)
if( *(i+1) - *i > horz)
horz = *(i+1) - *i;
if(horz < h- *(horizontalCuts.end() - 1))
horz = h- *(horizontalCuts.end() - 1);
if(vert < w- *(verticalCuts.end() - 1))
vert = w- *(verticalCuts.end() - 1);
return (horz * vert) % 1000000007 ;
}
};
int main()
{
Solution s;
vector<int> v;
v.push_back(2);
s.sortInPlace(v);
cout<<s.maxArea(1000000000,1000000000,v,v);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTx2ZWN0b3I+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNsYXNzIFNvbHV0aW9uCnsKcHVibGljOgogICAgdm9pZCBzb3J0SW5QbGFjZSh2ZWN0b3I8aW50PiYgdikKICAgIHsKICAgICAgICBpbnQgbGVuID0gdi5zaXplKCk7CiAgICAgICAgZm9yKGludCBpID0wOyBpIDxsZW4gOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgayA9IGk7CiAgICAgICAgICAgIHdoaWxlKGs+MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IHBhciA9IChrLTEpLzI7CiAgICAgICAgICAgICAgICBpZih2W2tdID4gdltwYXJdKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHN3YXAodltrXSx2W3Bhcl0pOwogICAgICAgICAgICAgICAgICAgIGsgPSBwYXI7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIGJyZWFrOwogICAgICAgICAgICB9CgogICAgICAgIH0KICAgICAgICBmb3IoaW50IGo9bGVuLTEgOyBqPjAgOyBqLS0pCiAgICAgICAgewogICAgICAgICAgICBzd2FwKHZbMF0sdltqXSk7CiAgICAgICAgICAgIGludCBrID0gMDsKICAgICAgICAgICAgd2hpbGUoMiprKzEgPCBqKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgbGVmdCA9IDIqayArMSA7CiAgICAgICAgICAgICAgICBpbnQgcmlnaHQgPSAyKmsgKzIgOwogICAgICAgICAgICAgICAgaW50IGxhcmdlc3QgPSBsZWZ0OwogICAgICAgICAgICAgICAgaWYocmlnaHQgPCBqICYmIHZbcmlnaHRdID4gdltsYXJnZXN0XSkKICAgICAgICAgICAgICAgICAgICBsYXJnZXN0ID0gcmlnaHQ7CiAgICAgICAgICAgICAgICBpZih2W2xhcmdlc3RdID4gdltrXSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBzd2FwKHZba10sdltsYXJnZXN0XSk7CiAgICAgICAgICAgICAgICAgICAgayA9IGxhcmdlc3Q7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgIH0KICAgIGludCBtYXhBcmVhKGludCBoLCBpbnQgdywgdmVjdG9yPGludD4mIGhvcml6b250YWxDdXRzLCB2ZWN0b3I8aW50PiYgdmVydGljYWxDdXRzKQogICAgewogICAgICAgIHNvcnRJblBsYWNlKHZlcnRpY2FsQ3V0cyk7CiAgICAgICAgc29ydEluUGxhY2UoaG9yaXpvbnRhbEN1dHMpOwogICAgICAgIGxvbmcgbG9uZyB2ZXJ0ID0gdmVydGljYWxDdXRzLmZyb250KCksaG9yeiA9IGhvcml6b250YWxDdXRzLmZyb250KCk7CiAgICAgICAgaW50IG1heCA9IDE7CiAgICAgICAgZm9yKHZlY3RvcjxpbnQ+OjppdGVyYXRvciBpID0gdmVydGljYWxDdXRzLmJlZ2luKCk7aSE9IHZlcnRpY2FsQ3V0cy5lbmQoKS0xO2krKykKICAgICAgICAgICAgaWYoICooaSsxKSAtICppID4gdmVydCkKICAgICAgICAgICAgICAgIHZlcnQgPSAqKGkrMSkgLSAqaTsKICAgICAgICBmb3IodmVjdG9yPGludD46Oml0ZXJhdG9yIGkgPSBob3Jpem9udGFsQ3V0cy5iZWdpbigpO2khPSBob3Jpem9udGFsQ3V0cy5lbmQoKS0xO2krKykKICAgICAgICAgICAgaWYoICooaSsxKSAtICppID4gaG9yeikKICAgICAgICAgICAgICAgIGhvcnogPSAqKGkrMSkgLSAqaTsKICAgICAgICBpZihob3J6IDwgaC0gKihob3Jpem9udGFsQ3V0cy5lbmQoKSAtIDEpKQogICAgICAgICAgICBob3J6ID0gaC0gKihob3Jpem9udGFsQ3V0cy5lbmQoKSAtIDEpOwoKICAgICAgICBpZih2ZXJ0IDwgdy0gKih2ZXJ0aWNhbEN1dHMuZW5kKCkgLSAxKSkKICAgICAgICAgICAgdmVydCA9IHctICoodmVydGljYWxDdXRzLmVuZCgpIC0gMSk7CiAgICAgICAgcmV0dXJuIChob3J6ICogdmVydCkgJSAxMDAwMDAwMDA3IDsKCgoKICAgIH0KfTsKaW50IG1haW4oKQp7CiAgICBTb2x1dGlvbiBzOwogICAgdmVjdG9yPGludD4gdjsKICAgIHYucHVzaF9iYWNrKDIpOwoKICAgIHMuc29ydEluUGxhY2Uodik7CiAgICBjb3V0PDxzLm1heEFyZWEoMTAwMDAwMDAwMCwxMDAwMDAwMDAwLHYsdik7CiAgICByZXR1cm4gMDsKfQ==