求助。为什么会RE？
- 板块P8818 [CSP-S 2022] 策略游戏
- 楼主i_wzy
- 当前回复2
- 已保存回复2
- 发布时间2024/11/23 16:55
- 上次更新2024/11/23 19:35:42
查看原帖
被骇客银狼阻止的越权访问保存失败
求助。为什么会RE？
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
using ll=long long ;
namespace IO{
template<typename Type>void read(Type &x){
x=0;int fl=0;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') fl=1;
ch=getchar();
}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(fl) x=-x;
}
template<typename Type>void print(Type x){
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar((int)(x%10)+'0');
}
template<typename Type>void print(Type x,char ch){
print(x),putchar(ch);
}
}using namespace IO;
const int N=2e5+10;
int n,m,q,a[N],b[N],log_2[N];
int l1,r1,l2,r2;
ll f[10][N][40];
void ST_prework(){
for(int i=2;i<=1e5;++i) log_2[i]=log_2[i/2]+1;
for(int i=1;i<=n;++i) f[0][i][0]=f[1][i][0]=a[i];
for(int i=1;i<=m;++i) f[2][i][0]=f[3][i][0]=b[i];
for(int k=1;k<=log_2[n];++k)
for(int i=1;i<=n;++i)
f[0][i][k]=max(f[0][i][k-1],f[0][i+(1<<(k-1))][k-1]),
f[1][i][k]=min(f[1][i][k-1],f[1][i+(1<<(k-1))][k-1]);
for(int k=1;k<=log_2[m];++k)
for(int i=1;i<=m;++i)
f[2][i][k]=min(f[2][i][k-1],f[2][i+(1<<(k-1))][k-1]),
f[3][i][k]=max(f[3][i][k-1],f[3][i+(1<<(k-1))][k-1]);
for(int i=1;i<=n;++i){
b[i]=a[i];
if(a[i]<0) a[i]=1e9;
if(b[i]>0) b[i]=-1e9;
}
for(int i=1;i<=n;++i) f[4][i][0]=a[i],f[5][i][0]=b[i];
for(int k=1;k<=log_2[n];++k)
for(int i=1;i<=n;++i)
f[4][i][k]=min(f[4][i][k-1],f[4][i+(1<<(k-1))][k-1]),
f[5][i][k]=max(f[5][i][k-1],f[5][i+(1<<(k-1))][k-1]);
}
ll ST_query_A_mx(int l,int r){
int k=log_2[r-l+1];
return max(f[0][l][k],f[0][r-(1<<k)+1][k]);
}
ll ST_query_A_mn(int l,int r){
int k=log_2[r-l+1];
return min(f[1][l][k],f[1][r-(1<<k)+1][k]);
}
ll ST_query_B_mn(int l,int r){
int k=log_2[r-l+1];
return min(f[2][l][k],f[2][r-(1<<k)+1][k]);
}
ll ST_query_B_mx(int l,int r){
int k=log_2[r-l+1];
return max(f[3][l][k],f[3][r-(1<<k)+1][k]);
}
ll ST_query_A_fmn(int l,int r){
int k=log_2[r-l+1];
return min(f[4][l][k],f[4][r-(1<<k)+1][k]);
}
ll ST_query_A_fmx(int l,int r){
int k=log_2[r-l+1];
return max(f[5][l][k],f[5][r-(1<<k)+1][k]);
}
void solve(){
ST_prework();
while(q--){
read(l1),read(r1),read(l2),read(r2);
ll amn=ST_query_A_mn(l1,r1),amx=ST_query_A_mx(l1,r1),
bmn=ST_query_B_mn(l2,r2),bmx=ST_query_B_mx(l2,r2);
if(amn<0){
if(amx<0){
if(bmn<0){
if(bmx<0) print(1ll*amn*bmx,'\n');
else print(1ll*amx*bmx,'\n');
}
else print(1ll*amx*bmx,'\n');
}
else{
if(bmn<0){
if(bmx<0) print(1ll*amn*bmx,'\n');
else{
ll res1=ST_query_A_fmx(l1,r1),res2=ST_query_A_fmn(l1,r1);
print(max(1ll*res2*bmn,1ll*res1*bmx),'\n');
}
}
else print(1ll*amx*bmn,'\n');
}
}
else{
if(bmn<0) print(amn*bmn,'\n');
else print(1ll*amx*bmn,'\n');
}
}
return ;
}
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(a[i]);
for(int i=1;i<=m;++i) read(b[i]);
solve();
return 0;
}
这份代码的 const int N=2e5+10; 改成 const int N=1e5+10; 为什么会出现 RE 的情况？
但是我分成部分分写开const int N=1e5+10;就没问题。这是什么原因？
这是部分分的代码：
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long ;
namespace IO{
template<typename Type>void read(Type &x){
x=0;int fl=0;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') fl=1;
ch=getchar();
}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(fl) x=-x;
}
template<typename Type>void print(Type x){
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar((int)(x%10)+'0');
}
template<typename Type>void print(Type x,char ch){
print(x),putchar(ch);
}
}using namespace IO;
const int N=1e5+10;
int n,m,q,a[N],b[N],log_2[N];
int l1,r1,l2,r2;
namespace bf{
std::vector<ll>c[1010];
ll f[1010][1010][11];
void ST_prework(){
for(int i=2;i<=1010;++i) log_2[i]=log_2[i/2]+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
f[i][j][0]=c[i][j];
for(int i=1;i<=n;++i)
for(int k=1;k<=log_2[m];++k)
for(int j=1;j+(1<<k)-1<=m;++j)
f[i][j][k]=min(f[i][j][k-1],f[i][j+(1<<(k-1))][k-1]);
}
ll ST_query(int x,int l,int r){
int k=log_2[r-l+1];
return min(f[x][l][k],f[x][r-(1<<k)+1][k]);
}
void solve(){
for(int i=1;i<=n;++i){
c[i].push_back(0);
for(int j=1;j<=m;++j)
c[i].push_back(1ll*a[i]*b[j]);
}
ST_prework();
ll ans=-1e18;
while(q--){
read(l1),read(r1),read(l2),read(r2),ans=-1e18;
for(int i=l1;i<=r1;++i) ans=max(ans,ST_query(i,l2,r2));
print(ans,'\n');
}
return ;
}
}
ll f[6][N][30];
namespace Spl{
//max:小L min:小Q
void ST_prework(){
for(int i=2;i<=1e5;++i) log_2[i]=log_2[i/2]+1;
for(int i=1;i<=n;++i) f[0][i][0]=a[i];
for(int i=1;i<=m;++i) f[1][i][0]=b[i];
for(int k=1;k<=log_2[n];++k)
for(int i=1;i<=n;++i)
f[0][i][k]=max(f[0][i][k-1],f[0][i+(1<<(k-1))][k-1]);
for(int k=1;k<=log_2[m];++k)
for(int i=1;i<=m;++i)
f[1][i][k]=min(f[1][i][k-1],f[1][i+(1<<(k-1))][k-1]);
}
ll ST_query_mx(int l,int r){
int k=log_2[r-l+1];
return max(f[0][l][k],f[0][r-(1<<k)+1][k]);
}
ll ST_query_mn(int l,int r){
int k=log_2[r-l+1];
return min(f[1][l][k],f[1][r-(1<<k)+1][k]);
}
void solve(){
ST_prework();
while(q--){
read(l1),read(r1),read(l2),read(r2);
print(ST_query_mx(l1,r1)*ST_query_mn(l2,r2),'\n');
}
return ;
}
}
namespace std{
void ST_prework(){
for(int i=2;i<=1e5;++i) log_2[i]=log_2[i/2]+1;
for(int i=1;i<=n;++i) f[0][i][0]=f[1][i][0]=a[i];
for(int i=1;i<=m;++i) f[2][i][0]=f[3][i][0]=b[i];
for(int k=1;k<=log_2[n];++k)
for(int i=1;i<=n;++i)
f[0][i][k]=max(f[0][i][k-1],f[0][i+(1<<(k-1))][k-1]),
f[1][i][k]=min(f[1][i][k-1],f[1][i+(1<<(k-1))][k-1]);
for(int k=1;k<=log_2[m];++k)
for(int i=1;i<=m;++i)
f[2][i][k]=min(f[2][i][k-1],f[2][i+(1<<(k-1))][k-1]),
f[3][i][k]=max(f[3][i][k-1],f[3][i+(1<<(k-1))][k-1]);
for(int i=1;i<=n;++i){
b[i]=a[i];
if(a[i]<0) a[i]=1e9;
if(b[i]>0) b[i]=-1e9;
}
for(int i=1;i<=n;++i) f[4][i][0]=a[i],f[5][i][0]=b[i];
for(int k=1;k<=log_2[n];++k)
for(int i=1;i<=n;++i)
f[4][i][k]=min(f[4][i][k-1],f[4][i+(1<<(k-1))][k-1]),
f[5][i][k]=max(f[5][i][k-1],f[5][i+(1<<(k-1))][k-1]);
}
ll ST_query_A_mx(int l,int r){
int k=log_2[r-l+1];
return max(f[0][l][k],f[0][r-(1<<k)+1][k]);
}
ll ST_query_A_mn(int l,int r){
int k=log_2[r-l+1];
return min(f[1][l][k],f[1][r-(1<<k)+1][k]);
}
ll ST_query_B_mn(int l,int r){
int k=log_2[r-l+1];
return min(f[2][l][k],f[2][r-(1<<k)+1][k]);
}
ll ST_query_B_mx(int l,int r){
int k=log_2[r-l+1];
return max(f[3][l][k],f[3][r-(1<<k)+1][k]);
}
ll ST_query_A_fmn(int l,int r){
int k=log_2[r-l+1];
return min(f[4][l][k],f[4][r-(1<<k)+1][k]);
}
ll ST_query_A_fmx(int l,int r){
int k=log_2[r-l+1];
return max(f[5][l][k],f[5][r-(1<<k)+1][k]);
}
void solve(){
ST_prework();
while(q--){
read(l1),read(r1),read(l2),read(r2);
ll amn=ST_query_A_mn(l1,r1),amx=ST_query_A_mx(l1,r1),
bmn=ST_query_B_mn(l2,r2),bmx=ST_query_B_mx(l2,r2);
if(amn<0){
if(amx<0){
if(bmn<0){
if(bmx<0) print(1ll*amn*bmx,'\n');
else print(1ll*amx*bmx,'\n');
}
else print(1ll*amx*bmx,'\n');
}
else{
if(bmn<0){
if(bmx<0) print(1ll*amn*bmx,'\n');
else{
ll res1=ST_query_A_fmx(l1,r1),res2=ST_query_A_fmn(l1,r1);
print(max(1ll*res2*bmn,1ll*res1*bmx),'\n');
}
}
else print(1ll*amx*bmn,'\n');
}
}
else{
if(bmn<0) print(amn*bmn,'\n');
else print(1ll*amx*bmn,'\n');
}
}
return ;
}
}
int main(){
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
read(n),read(m),read(q);
bool flag=true;
for(int i=1;i<=n;++i){
read(a[i]);
if(a[i]<0) flag=false;
}
for(int i=1;i<=m;++i){
read(b[i]);
if(b[i]<0) flag=false;
}
if(n<=1000&&m<=1000) bf::solve();
else if(flag) Spl::solve();
else std::solve();
return 0;
}
加载中...