| 记录编号 |
587107 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[CSP 2022S]策略游戏 |
最终得分 |
100 |
| 用户昵称 |
 宇战 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
5.241 s |
| 提交时间 |
2024-03-13 20:46:34 |
内存使用 |
20.60 MiB |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,a[400000],aa[400000],b[400000],q,la,laa;
struct nodee{
int l,r,mx,mn;
}t[400002];//维护a的非负数最大值和最小值
struct nodeee{
int l,r,mx,mn;
}tt[400002];//维护a的负数最大值最小值
struct nodeeee{
int l,r,mx,mn;
}ttt[400002];//维护b的最大值最小值
void build(int p,int l,int r,int opt,int pos,int v){
t[p].l=l;
t[p].r=r;
if(l==r){
if(opt)t[p].mx=-1e18,t[p].mn=1e18;
else t[p].mx=t[p].mn=v;
return;
}
int mid=(l+r)/2;
if (pos<=mid)build(p*2,l,mid,opt,pos,v);
else build(p*2+1,mid+1,r,opt,pos,v);
t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
t[p].mn=min(t[p*2].mn,t[p*2+1].mn);
}
void buildd(int p,int l,int r,int opt,int pos,int v){
tt[p].l=l;
tt[p].r=r;
if(l==r){
if(opt)tt[p].mx=-1e18,tt[p].mn=1e18;
else tt[p].mx=tt[p].mn=v;
return;
}
int mid=(l+r)/2;
if (pos<=mid)buildd(p*2,l,mid,opt,pos,v);
else buildd(p*2+1,mid+1,r,opt,pos,v);
tt[p].mx=max(tt[p*2].mx,tt[p*2+1].mx);
tt[p].mn=min(tt[p*2].mn,tt[p*2+1].mn);
}
void builddd(int p,int l,int r){
ttt[p].l=l;
ttt[p].r=r;
if(l==r){
ttt[p].mx=ttt[p].mn=b[l];
return;
}
int mid=(l+r)/2;
builddd(p*2,l,mid);
builddd(p*2+1,mid+1,r);
ttt[p].mx=max(ttt[p*2].mx,ttt[p*2+1].mx);
ttt[p].mn=min(ttt[p*2].mn,ttt[p*2+1].mn);
}
int ax(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].mx;
}
int mid=(t[p].l+t[p].r)/2;
int val=-1e18;
if(l<=mid)val=max(val,ax(p*2,l,r));
if(r>mid)val=max(val,ax(p*2+1,l,r));
return val;
}
int aax(int p,int l,int r){
if(l<=tt[p].l&&tt[p].r<=r){
return tt[p].mx;
}
int mid=(tt[p].l+tt[p].r)/2;
int val=-1e18;
if(l<=mid)val=max(val,aax(p*2,l,r));
if(r>mid)val=max(val,aax(p*2+1,l,r));
return val;
}
int bx(int p,int l,int r){
if(l<=ttt[p].l&&ttt[p].r<=r){
return ttt[p].mx;
}
int mid=(ttt[p].l+ttt[p].r)/2;
int val=-1e18;
if(l<=mid)val=max(val,bx(p*2,l,r));
if(r>mid)val=max(val,bx(p*2+1,l,r));
return val;
}
int an(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].mn;
}
int mid=(t[p].l+t[p].r)/2;
int val=1e18;
if(l<=mid)val=min(val,an(p*2,l,r));
if(r>mid)val=min(val,an(p*2+1,l,r));
return val;
}
int aan(int p,int l,int r){
if(l<=tt[p].l&&tt[p].r<=r){
return tt[p].mn;
}
int mid=(tt[p].l+tt[p].r)/2;
int val=1e18;
if(l<=mid)val=min(val,aan(p*2,l,r));
if(r>mid)val=min(val,aan(p*2+1,l,r));
return val;
}
int bn(int p,int l,int r){
if(l<=ttt[p].l&&ttt[p].r<=r){
return ttt[p].mn;
}
int mid=(ttt[p].l+ttt[p].r)/2;
int val=1e18;
if(l<=mid)val=min(val,bn(p*2,l,r));
if(r>mid)val=min(val,bn(p*2+1,l,r));
return val;
}
signed main(){
freopen("csp2022_game.in","r",stdin);
freopen("csp2022_game.out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x>=0){
build(1,1,n,0,i,x);
buildd(1,1,n,1,i,x);
}else{
build(1,1,n,1,i,x);
buildd(1,1,n,0,i,x);
}
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
builddd(1,1,m);
while(q--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
int maxz=ax(1,l1,r1);
int minz=an(1,l1,r1);
int maxf=aax(1,l1,r1);
int minf=aan(1,l1,r1);
int maxb=bx(1,l2,r2);
int minb=bn(1,l2,r2);
int ans1,ans2,ans3,ans4;
if(maxz>=0){
ans1=maxz*minb;
}else{
ans1=-1e18;
}
if(minz<1e18){
ans2=minz*minb;
}else{
ans2=-1e18;
}
if(maxf>-1e18){
ans3=maxf*maxb;
}else{
ans3=-1e18;
}
if(minf<0){
ans4=minf*maxb;
}else{
ans4=-1e18;
}
cout<<max(ans1,max(ans2,max(ans3,ans4)))<<endl;
}
return 0;
}