WA50求助
查看原帖
WA50求助
371848
吴思诚楼主2023/9/25 21:28

之前用了8个数组维护,但是只需要6个,而且马蜂丑,所以修改改了一下,但是WA了

#include<cstdio>
#include<algorithm>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
typedef long long ll;

const int N=100010,M=17;
const ll INF=1e9+1;
int n,m,q,a[N],b[N],LOG[N],amx[M][N],amn[M][N],bmx[M][N],bmn[M][N],fmx[M][N],zmn[M][N];
void init(int mn[][N],int mx[][N],int n,int a[]){
    E(i, n)mn[0][i]=mx[0][i]=a[i];
    E(i, LOG[n])
        for(int j=1;j+(1<<i)-1<=n;++j){
            mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
            mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
        }
}
void Init(){
    E(i, n){
        fmx[0][i]=a[i]<=0?a[i]:-INF;
        zmn[0][i]=a[i]>=0?a[i]:INF;
    }
    E(i, LOG[n])
        for(int j=1;j+(1<<i)-1<=n;++j){
            zmn[i][j]=min(zmn[i-1][j],zmn[i-1][j+(1<<i-1)]);
            fmx[i][j]=max(fmx[i-1][j],fmx[i-1][j+(1<<i-1)]);
        }
}
int qmax(int f[][N],int l,int r){
    int k=LOG[r-l+1];
    return max(f[k][l],f[k][r-(1<<k)+1]);
}
int qf(int l,int r){
    int k=LOG[r-l+1];
    return max(fmx[k][l],fmx[k][r-(1<<k)+1]);
}
int qz(int l,int r){
    int k=LOG[r-l+1];
    return min(zmn[k][l],zmn[k][r-(1<<k)+1]);
}
int qmin(int f[][N],int l,int r){
    int k=LOG[r-l+1];
    return min(f[k][l],f[k][r-(1<<k)+1]);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    scanf("%d%d%d",&n,&m,&q);
    int lim=max(n,m);
    Le(i, 2, lim)LOG[i]=LOG[i>>1]+1;
    E(i, n)scanf("%d",a+i);
    E(i, m)scanf("%d",b+i);
    init(amn,amx,n,a);
    init(bmn,bmx,m,b);
    Init();
    W(q){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        ll amax=qmax(amx,l1,r1),amin=qmin(amn,l1,r1);
        ll bmax=qmax(bmx,l2,r2),bmin=qmin(bmn,l2,r2);
        ll ans;
        int state=((amax>=0)|(amin<=0)<<1)*3-3+((bmax>=0)|(bmin<=0)<<1)-1;
        if(!state||state==3||state==6)ans=amax*bmin;
        else if(state==1||state==2)ans=amin*bmin;
        else if(state==4||state==7)ans=amin*bmax;
        else if(state==5)ans=amax*bmax;
        else{
            ll fmax=qf(l1,r1),zmin=qz(l1,r1);
            ans=max(zmin*bmin,fmax*bmax);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

请大佬们帮我看看,谢谢

2023/9/25 21:28
加载中...