5. CSP2022-S-2-策略游戏
\color{red}Wrong Answer 80分
代码奉上
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int b[100005];
int f[231073][25],f1[231073][25];
int f2[231073][25],f3[231073][25];
int f4[231073][25],f5[231073][25];
int lg[231073];
int n,q,l1,r1,l2,r2,m;
int cnt;
bool gmx(int &a,int b){
if(a>b){
a = b;
return 1;
}else{
return 0;
}
}
signed main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
cin>>n;
cin>>m;
cin>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][0]=a[i];
f1[i][0]=a[i];
if(a[i]>=0){
f3[i][0]=a[i];
f2[i][0]=LONG_LONG_MIN;
}else{
f2[i][0]=a[i];
f3[i][0]=LONG_LONG_MAX;
}
}
for(int i=1;i<=m;i++){
cin>>b[i];
f4[i][0]=b[i];
f5[i][0]=b[i];
}
for(int i = 2;i<=max(n,m);i++){
lg[i]=lg[i>>1]+1;
}
for(int j = 1;(1<<(j-1))<=n;j++){
int d = (1<<(j-1));
for(int i=1;i<=n;i++){
f[i][j]=max(f[i][j-1],f[i+d][j-1]);
f1[i][j]=min(f1[i][j-1],f1[i+d][j-1]);
f2[i][j]=max(f2[i][j-1],f2[i+d][j-1]);
f3[i][j]=min(f3[i][j-1],f3[i+d][j-1]);
}
}
for(int j = 1;(1<<(j-1))<=n;j++){
int d = (1<<(j-1));
for(int i=1;i<=n;i++){
f4[i][j]=max(f4[i][j-1],f4[i+d][j-1]);
f5[i][j]=min(f5[i][j-1],f5[i+d][j-1]);
}
}
while(q--){
cin>>l1>>r1>>l2>>r2;
int s1 = lg[r1-l1+1],s2 = lg[r2-l2+1];
int p1 = r1 - (1<<s1)+1,p2 = r2 - (1<<s2)+1;
int amax = max(f[l1][s1],f[p1][s1]);
int amin = min(f1[l1][s1],f1[p1][s1]);
int afmx = max(f2[l1][s1],f2[p1][s1]);
int azmn = min(f3[l1][s1],f3[p1][s1]);
int bmax = max(f4[l2][s2],f4[p2][s2]);
int bmin = min(f5[l2][s2],f5[p2][s2]);
//cout<<amax<<" "<<amin<<" "<<afmx<<" "<<azmn<<" "<<bmax<<" "<<bmin<<endl;
int ans = LONG_LONG_MIN;
if(amin>=0){
if(bmin>=0){
ans=amax*bmin;
}
else
ans=amin*bmin;
}else if(amax<0){
if(bmax<0){
ans=amin*bmax;
}else{
ans=amax*bmax;
}
}else{
if(bmin>=0){
ans=amax*bmin;
}else if(bmax<0){
ans=amin*bmax;
}else{
ans=max(azmn*bmin,afmx*bmax);
}
}
cout<<ans<<'\n';
}
return 0;
}
