文件详细信息

下载本文件

本文件的大小为 2612 字节。

#include<cstdio>
void read(int&num){
	bool flag=true;
	int ch=getchar();
	num=0;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	flag||(num=-num);
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
namespace my_std{
	inline int max(const int a,const int b){
		return a>b?a:b;
	}
	inline int min(const int a,const int b){
		return a<b?a:b;
	}
	void chkmax(ll&a,const ll b){
		if(a<b)a=b;
	}
	void chkmin(ll&a,const ll b){
		if(a>b)a=b;
	}
};
const int maxn=100005,inf=0x3f3f3f3f;
struct Seg{
	int l,r,mx,mn,mx_pos,mn_pos,mx_neg,mn_neg,zero;
};
struct Seg_Tree{
	int a[maxn];
	Seg T[maxn*2];
	void pushup(Seg&u,const Seg l,const Seg r){
		u.mx=my_std::max(l.mx,r.mx);
		u.mn=my_std::min(l.mn,r.mn);
		u.mx_pos=my_std::max(l.mx_pos,r.mx_pos);
		u.mn_pos=my_std::min(l.mn_pos,r.mn_pos);
		u.mx_neg=my_std::max(l.mx_neg,r.mx_neg);
		u.mn_neg=my_std::min(l.mn_neg,r.mn_neg);
		u.zero=l.zero|r.zero;
	}
	int tot,rt;
	void build(int&u,int l,int r){
		u=++tot;
		if(l==r){
			T[u].mx=T[u].mn=a[l];
			T[u].mx_pos=(a[l]>0)?a[l]:-inf;
			T[u].mn_pos=(a[l]>0)?a[l]:inf;
			T[u].mx_neg=(a[l]<0)?a[l]:-inf;
			T[u].mn_neg=(a[l]<0)?a[l]:inf;
			T[u].zero=(a[l]==0);
			return;
		}
		int m=(l+r)>>1;
		build(T[u].l,l,m);
		build(T[u].r,m+1,r);
		pushup(T[u],T[T[u].l],T[T[u].r]);
	}
	int ql,qr;
	Seg query(int u,int l,int r){
		if(ql<=l&&r<=qr)return T[u];
		int m=(l+r)>>1;
		if(qr<=m)return query(T[u].l,l,m);
		if(ql>m)return query(T[u].r,m+1,r);
		Seg ans;
		pushup(ans,query(T[u].l,l,m),query(T[u].r,m+1,r));
		return ans;
	}
}Ta,Tb;
int n,m,q;
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	read(n),read(m),read(q);
	for(int i=1;i<=n;i++)read(Ta.a[i]);
	Ta.build(Ta.rt,1,n);
	for(int i=1;i<=m;i++)read(Tb.a[i]);
	Tb.build(Tb.rt,1,m);
	ll pos_ans,neg_ans,ans;
	for(int i=1;i<=q;i++){
		read(Ta.ql),read(Ta.qr),read(Tb.ql),read(Tb.qr);
		Seg ans1=Ta.query(Ta.rt,1,n),ans2=Tb.query(Tb.rt,1,m);
		ans=-2e18;
		if(ans1.mx_pos!=-inf){
			if(ans2.mn<0)pos_ans=(ll)ans1.mn_pos*ans2.mn;
			else if(ans2.mn==0)pos_ans=0;
			else pos_ans=(ll)ans1.mx_pos*ans2.mn;
			my_std::chkmax(ans,pos_ans);
		}
		if(ans1.mx_neg!=-inf){
			if(ans2.mx<0)neg_ans=(ll)ans1.mn_neg*ans2.mx;
			else if(ans2.mx==0)neg_ans=0;
			else neg_ans=(ll)ans1.mx_neg*ans2.mx;
			my_std::chkmax(ans,neg_ans);
		}
		if(ans1.zero)my_std::chkmax(ans,0);
		write(ans),putchar('\n');
	}
	return 0;
}