| 记录编号 |
607641 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
3782.[CSP 2022S]策略游戏 |
最终得分 |
100 |
| 用户昵称 |
 孤独的氢离子 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
5.000 s |
| 提交时间 |
2025-10-19 16:35:56 |
内存使用 |
41.40 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e9+ 10;
long long a[100010],b[100010],faa[100010][20],fai[100010][20],faz[100010][20],faf[100010][20],fba[100010][20],fbi[100010][20];
long long queryMax(long long a1[100010][20], int l, int r)
{
int t = log2(r - l + 1);
return max(a1[l][t], a1[r - (1 << t) + 1][t]);
}
long long queryMin(long long a1[100010][20], int l, int r)
{
int t = log2(r - l + 1);
return min(a1[l][t], a1[r - (1 << t) + 1][t]);
}
int main()
{
freopen("csp2022_game.in","r",stdin);
freopen("csp2022_game.out","w",stdout);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
faa[i][0]=a[i];fai[i][0]=a[i];
if(a[i]>0)
{
faz[i][0]=a[i];
faf[i][0]=-1*INF;
}
else if(a[i]<0)
{
faf[i][0]=a[i];
faz[i][0]=INF;
}
else
{
faz[i][0]=0;
faf[i][0]=0;
}
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
fba[i][0]=b[i];fbi[i][0]=b[i];
}
for(int i=1;i<=16;i++)
for(int j=1;j<=n-(1<<i)+1;j++)
{
faa[j][i]=max(faa[j][i-1],faa[j+(1<<(i-1))][i-1]);
fai[j][i]=min(fai[j][i-1],fai[j+(1<<(i-1))][i-1]);
faz[j][i]=min(faz[j][i-1],faz[j+(1<<(i-1))][i-1]);
faf[j][i]=max(faf[j][i-1],faf[j+(1<<(i-1))][i-1]);
}
for(int i=1;i<=16;i++)
for(int j=1;j<=m-(1<<i)+1;j++)
{
fba[j][i]=max(fba[j][i-1],fba[j+(1<<(i-1))][i-1]);
fbi[j][i]=min(fbi[j][i-1],fbi[j+(1<<(i-1))][i-1]);
}
for(int i=1;i<=q;i++)
{
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
long long ama=queryMax(faa,l1,r1);
long long azmi=queryMin(faz,l1,r1);
long long ami=queryMin(fai,l1,r1);
long long afma=queryMax(faf,l1,r1);
long long bma=queryMax(fba,l2,r2);
long long bmi=queryMin(fbi,l2,r2);
// cout<<ama<<" "<<azmi<<" "<<afma<<" "<<ami<<" "<<bma<<" "<<bmi<<" "<<endl<<" ";
long long ans=0;
if(bmi>=0)
{
if(ama<=0) ans=ama*bma;
else ans=ama*bmi;
}
else if(bma<=0)
{
if(ami>=0) ans=ami*bmi;
else ans=ami*bma;
}
else
{
if(ami>=0) ans=ami*bmi;
else if(ama<=0) ans=afma*bma;
else ans=max(bma*afma,bmi*azmi);
}
cout<<ans<<endl;
// long long azma=0,azmi=0,afma=0,afmi=0,bzma=0,bzmi=0,bfma=0,bfmi=0;
// for(int l=l1;l<=r1;l++)
// {
// if(a[l]==0)
// {
// azmi=0;
// afmi=0;
// }
// else if(a[l]>0)
// {
// if(azma==0)
// {
// azma=a[l];
// azmi=a[l];
// }
// else
// {
// if(a[l]>azma)
// {
// azma=a[l];
// }
// else if(a[l]<azmi)
// {
// azmi=a[l];
// }
// }
// }
// else if(a[l]<0)
// {
// if(afma==0)
// {
// afma=a[l];
// afmi=a[l];
// }
// else{
// if(a[l]<afma)
// {
// afma=a[l];
// }
// else if(a[l]>afmi)
// {
// afmi=a[l];
// }
// }
// }
// }
// for(int l=l2;l<=r2;l++)
// {
// if(b[l]==0)
// {
// bzmi=0;
// bfmi=0;
// }
// else if(b[l]>0)
// {
// if(bzma==0)
// {
// bzma=b[l];
// bzmi=b[l];
// }
// else
// {
// if(b[l]>bzma)
// {
// bzma=b[l];
// }
// else if(b[l]<bzmi)
// {
// bzmi=b[l];
// }
// }
// }
// else if(b[l]<0)
// {
// if(bfma==0)
// {
// bfma=b[l];
// bfmi=b[l];
// }
// else{
// if(b[l]<bfma)
// {
// bfma=b[l];
// }
// else if(b[l]>bfmi)
// {
// bfmi=b[l];
// }
// }
// }
// }
// long long ans=0;
// if((bfma==0&&bzma==0)||(afma==0&&azma==0)) ans=0;
// else if(bfma==0)
// {
// if(azma!=0) ans=azma*bzmi;
// else ans=afmi*bzma;
// }
// else if(bzma==0)
// {
// if(afma!=0) ans=afma*bfmi;
// else ans=azmi*bfma;
// }
// else if(bfma!=0&&bzma!=0)
// {
// if(a0==0) ans==0;
// else if(afma==0) ans=bfma*azmi;
// else if(azma==0) ans=bzma*afmi;
// else if(bfma!=0&&bzma!=0) ans=max(bzma*afmi,bfma*azmi);
// }
// cout<<ans<<endl;
}
return 0;
}