| 记录编号 |
577461 |
评测结果 |
AAAWAAAAAAWWAAAAATTT |
| 题目名称 |
[CSP 2022S]策略游戏 |
最终得分 |
70 |
| 用户昵称 |
 康尚诚 |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
5.246 s |
| 提交时间 |
2022-11-04 19:22:55 |
内存使用 |
7.79 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const long long N=100010,INF=1e9+100;
long long a[N],b[N];
long long n,m,q;
long long amx[N*4],bmx[N*4],amn[N*4],bmn[N*4];//四棵线段树
void build_a(long long type,long long l=1,long long r=n,long long p=1)//建a数组的树:树的种类(1->max,2->min),当前建树的左区间和右区间,当前节点编号
{
if(type==1)//max tree
{
if(l==r)
{
amx[p]=a[l];
return;
}
long long mid=(l+r)/2;
build_a(type,l,mid,p*2);
build_a(type,mid+1,r,p*2+1);
amx[p]=max(amx[p*2],amx[p*2+1]);
}
else if(type==2)
{
if(l==r)
{
amn[p]=a[l];
return;
}
long long mid=(l+r)/2;
build_a(type,l,mid,p*2);
build_a(type,mid+1,r,p*2+1);
amn[p]=min(amn[p*2],amn[p*2+1]);
}
}
void build_b(long long type,long long l=1,long long r=m,long long p=1)//建b数组的树:树的种类(1->max,2->min),当前建树的左区间和右区间,当前节点编号
{
if(type==1)//max tree
{
if(l==r)
{
bmx[p]=b[l];
return;
}
long long mid=(l+r)/2;
build_b(type,l,mid,p*2);
build_b(type,mid+1,r,p*2+1);
bmx[p]=max(bmx[p*2],bmx[p*2+1]);
}
else if(type==2)
{
if(l==r)
{
bmn[p]=b[l];
return;
}
long long mid=(l+r)/2;
build_b(type,l,mid,p*2);
build_b(type,mid+1,r,p*2+1);
bmn[p]=min(bmn[p*2],bmn[p*2+1]);
}
}
long long mx_a(long long cl,long long cr,long long l=1,long long r=n,long long p=1)
{
if(cl>r||cr<l)
return -INF;
if(l>=cl&&r<=cr)//当前搜的区间在目标区间内
return amx[p];
else
{
long long mid=(l+r)/2;
return max(mx_a(cl,cr,l,mid,p*2),mx_a(cl,cr,mid+1,r,p*2+1));
}
}
long long mn_a(long long cl,long long cr,long long l=1,long long r=n,long long p=1)
{
if(cl>r||cr<l)
return INF;
if(l>=cl&&r<=cr)//当前搜的区间在目标区间内
return amn[p];
else
{
long long mid=(l+r)/2;
return min(mn_a(cl,cr,l,mid,p*2),mn_a(cl,cr,mid+1,r,p*2+1));
}
}
long long mx_b(long long cl,long long cr,long long l=1,long long r=m,long long p=1)
{
if(cl>r||cr<l)
return -INF;
if(l>=cl&&r<=cr)//当前搜的区间在目标区间内
return bmx[p];
else
{
long long mid=(l+r)/2;
return max(mx_b(cl,cr,l,mid,p*2),mx_b(cl,cr,mid+1,r,p*2+1));
}
}
long long mn_b(long long cl,long long cr,long long l=1,long long r=m,long long p=1)
{
if(cl>r||cr<l)
return INF;
if(l>=cl&&r<=cr)//当前搜的区间在目标区间内
return bmn[p];
else
{
long long mid=(l+r)/2;
return min(mn_b(cl,cr,l,mid,p*2),mn_b(cl,cr,mid+1,r,p*2+1));
}
}
long long arrmn(long long arr[],long long l,long long r)
{
long long mn=INF;
for(int i=l;i<=r;i++)
{
mn=min(mn,arr[i]);
}
return mn;
}
int main()
{
freopen("csp2022_game.in","r",stdin);
freopen("csp2022_game.out","w",stdout);
bool allzheng=true;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<0)
allzheng=false;
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
if(b[i]<0)
allzheng=false;
}
build_a(1);build_a(2);
build_b(1);build_b(2);
long long l1,r1,l2,r2;
for(int i=1;i<=q;i++)
{
cin>>l1>>r1>>l2>>r2;
// cout<<mx_a(l1,r1)<<' '<<mn_a(l1,r1)<<' '<<mx_b(l2,r2)<<' '<<mn_b(l2,r2)<<endl;
if(l1==r1)
{
if(a[l1]>=0)
{
cout<<a[l1]*mn_b(l2,r2)<<endl;
}
else
{
cout<<a[l1]*mx_b(l2,r2)<<endl;
}
}
else if(l2==r2)
{
if(b[l2]>=0)
{
cout<<b[l2]*mx_a(l1,r1)<<endl;
}
else
{
cout<<b[l2]*mn_a(l1,r1)<<endl;
}
}
else if(allzheng)
{
cout<<mx_a(l1,r1)*mn_b(l2,r2);
}
else
{
long long maxa=mx_a(l1,r1),mina=mn_a(l1,r1),maxb=mx_b(l2,r2),minb=mn_b(l2,r2);
if(maxa>=0&&mina<=0)
{
if(minb>=0)
{
cout<<maxa*minb<<endl;
}
else if(maxb<=0)
{
cout<<mina*maxb<<endl;
}
else
{
long long zhengmin=INF,fumax=-INF;
for(int i=l1;i<=r1;i++)
{
if(a[i]>0)
{
zhengmin=min(zhengmin,a[i]);
}
else
{
fumax=max(fumax,a[i]);
}
}
cout<<max(zhengmin*minb,fumax*maxb)<<endl;
}
}
else if(mina>=0)
{
cout<<mina*minb<<endl;
}
else if(maxa<=0)
{
if(maxb<=0)
{
cout<<mina*maxb<<endl;
}
else
{
cout<<maxa*maxb<<endl;
}
}
}
}
return 0;
}