WA on 20求调
查看原帖
WA on 20求调
169764
A350_ti楼主2022/11/1 12:32

RT,开了6个st表但是一直WA on 20

有没有热心dalao帮忙调一下啊/kel

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int LOGMAX=20;
const long long LNF=0xcfcfcfcfcfcfcfcfLL;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
#define int long long
int a[N];
int b[N];
int f[N][LOGMAX];//Amax 
int g[N][LOGMAX];//Bmin 
int h[N][LOGMAX];//Amin
int u[N][LOGMAX];//Bmax
int p[N][LOGMAX];//A>=0min
int rr[N][LOGMAX];//A<0max
int logn[N];
int n,m,q;
void yuchuli(){
	logn[1]=0;logn[2]=1;
	for(int i=3;i<N;i++)
		logn[i]=logn[i/2]+1;
	memset(f,0xcf,sizeof(f)),memset(g,0x3f,sizeof(g)),memset(h,0x3f,sizeof(h)),
	memset(u,0xcf,sizeof(u)),memset(p,0x3f,sizeof(p)),memset(rr,0xcf,sizeof(rr));
	for(int i=1;i<=n;i++){
		if(a[i]>=0)p[i][0]=a[i],f[i][0]=a[i];
		if(a[i]<0)rr[i][0]=a[i],h[i][0]=a[i];
	}
	for(int i=1;i<=m;i++){
		g[i][0]=b[i],u[i][0]=b[i];
	}
	for(int j=1;j<LOGMAX;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)//A>=0max 
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for(int j=1;j<LOGMAX;j++)
		for(int i=1;i+(1<<j)-1<=m;i++)//Bmin 
			g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);		
	for(int j=1;j<LOGMAX;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)//A<0min
			h[i][j]=min(h[i][j-1],h[i+(1<<(j-1))][j-1]);
	for(int j=1;j<LOGMAX;j++)
		for(int i=1;i+(1<<j)-1<=m;i++)//Bmax
			u[i][j]=max(u[i][j-1],u[i+(1<<(j-1))][j-1]);
	for(int j=1;j<LOGMAX;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)//A>=0min
			p[i][j]=min(p[i][j-1],p[i+(1<<(j-1))][j-1]);
	for(int j=1;j<LOGMAX;j++)
		for(int i=1;i+(1<<j)-1<=m;i++)//A<0max
			rr[i][j]=max(rr[i][j-1],rr[i+(1<<(j-1))][j-1]);				
}
int askf(int l,int r){
	int k=logn[r-l+1];
	int maxf=max(f[l][k],f[r-(1<<k)+1][k]);
	return maxf;
}
int askg(int l,int r){
	int k=logn[r-l+1];
	int maxg=min(g[l][k],g[r-(1<<k)+1][k]);
	return maxg;	
}
int askh(int l,int r){
	int k=logn[r-l+1];
	int maxh=min(h[l][k],h[r-(1<<k)+1][k]);
	return maxh;
}
int asku(int l,int r){
	int k=logn[r-l+1];
	int maxu=max(u[l][k],u[r-(1<<k)+1][k]);
	return maxu;	
}
int askp(int l,int r){
	int k=logn[r-l+1];
	int maxp=min(p[l][k],p[r-(1<<k)+1][k]);
	return maxp;	
}
int askr(int l,int r){
	int k=logn[r-l+1];
	int maxr=max(rr[l][k],rr[r-(1<<k)+1][k]);
	return maxr;
}
signed main(){	
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		cin>>b[i];
	yuchuli();
	
	int l1,r1,l2,r2,ans;
	while(q--){
		ans=LNF;
		scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
		int A1max=askf(l1,r1),Bmin=askg(l2,r2),A0min=askh(l1,r1),Bmax=asku(l2,r2),A1min=askp(l1,r1),A0max=askr(l1,r1);
		if(A1max!=LNF)ans=max(ans,A1max*Bmin);
		if(A1min!=INF)ans=max(ans,A1min*Bmin);
		if(A0max!=LNF)ans=max(ans,A0max*Bmax);
		if(A0min!=INF)ans=max(ans,A0min*Bmax);
		cout<<ans<<endl;
	}
	return 0;
}
2022/11/1 12:32
加载中...