题目描述

题解:

答案显然是$max((q-p)*(e-d))$

依然先贪心。

对于工厂,我们倾向于$pi<pj,di<dj$的;

对于买家,我们倾向于$qi>qj,ei>ej$的。

于是将一定不是最优解的工厂和买家划掉。

然后我们发现这个东西是满足决策单调性的。

问我怎么证?画一个二维坐标系,然后将选中的点都画上,然后就理性易证了。

最后分治。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 500050
#define ll long long
inline ll rd()
{
ll f=,c=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){c=*c+ch-'';ch=getchar();}
return f*c;
}
int n0,m0,n,m;
struct Pair
{
ll x,y;
Pair(){}
Pair(ll x,ll y):x(x),y(y){}
};
bool cmp1(Pair a,Pair b)
{
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
bool cmp2(Pair a,Pair b)
{
if(a.x!=b.x)return a.x<b.x;
return a.y>b.y;
}
Pair a0[N],b0[N],a[N],b[N];
ll ans = ;
void divi(int l1,int r1,int l2,int r2)
{
if(l1>r1||l2>r2)return ;
if(l1==r1)
{
for(int i=l2;i<=r2;i++)
if(b[i].x>a[l1].x)ans = max(ans,(b[i].x-a[l1].x)*(b[i].y-a[l1].y));
return ;
}
if(l2==r2)
{
for(int i=l1;i<=r1;i++)
if(b[l2].x>a[i].x)ans = max(ans,(b[l2].x-a[i].x)*(b[l2].y-a[i].y));
return ;
}
int mid = (l2+r2)>>;
int pos=l1;
ll max_val=-0x3f3f3f3f3f3f3f3fll;
for(int i=l1;i<=r1;i++)
{
if(b[mid].x<=a[i].x&&b[mid].y<=a[i].y)continue;
if((b[mid].x-a[i].x)*(b[mid].y-a[i].y)>max_val)
{
pos = i;
max_val=(b[mid].x-a[i].x)*(b[mid].y-a[i].y);
}
}
ans=max(ans,max_val);
divi(l1,pos,l2,mid-);
divi(pos,r1,mid+,r2);
}
int main()
{
// freopen("33.in","r",stdin);
n0 = rd(),m0 = rd();
for(int i=;i<=n0;i++)
a0[i].x = rd(),a0[i].y = rd();
for(int i=;i<=m0;i++)
b0[i].x = rd(),b0[i].y = rd();
sort(a0+,a0++n0,cmp1);
sort(b0+,b0++m0,cmp2);
ll lim = 0x3f3f3f3f3f3f3f3fll;
for(int i=;i<=n0;i++)
if(a0[i].y<lim)
{
a[++n]=a0[i];
lim = a0[i].y;
}
for(int i=;i<=m0;i++)
{
while(m&&b[m].y<=b0[i].y)m--;
b[++m]=b0[i];
}
divi(,n,,m);
printf("%lld\n",ans);
return ;
}

最新文章

  1. HTML5 学习笔记(三)——本地存储
  2. SASS 编译后去掉缓存文件和map文件
  3. 161229、SpringMVC的各种参数绑定方式
  4. AVSampleBufferDisplayLayer----转
  5. Java中Comparable和Comparator区别小结
  6. 靠边伸缩菜单的做法(类似QQ,碰到就会伸出来)
  7. ios多线程和进程的区别(转载)
  8. ios专题 - GCD(2)
  9. 怎么查看mysql执行过的sql。
  10. sql语句批量处理Batch
  11. [DeeplearningAI笔记]ML strategy_2_3迁移学习/多任务学习
  12. ios2048小游戏
  13. Ascall 码特殊字符——去除从windows上传文件的^M
  14. the first simple html page generated by div and table tags
  15. 关于Java的异常
  16. 插件开发之360 DroidPlugin源码分析(三)Binder代理
  17. mapreduce项目中加入combiner
  18. python之format函数
  19. Bootstrap关闭子类页面,刷新父类页面
  20. tomcat双击startup.bat启动时闪退

热门文章

  1. PTA 2-1 列出连通集【DFS+BFS基础】
  2. 二分优化的lis
  3. SVG新手入门
  4. LuoguP2115 [USACO14MAR]破坏Sabotage【二分答案】By cellur925
  5. Centos 6.x 搭建 Zabbix Server
  6. 喵哈哈村的魔法考试 Round #3 (Div.2) ABCDE
  7. Codeforces Round #405 (rated, Div. 2, based on VK Cup 2017 Round 1) E
  8. 洛谷 P2714 四元组统计
  9. DNS练习之正向解析
  10. Suricata的总体架构