为什么不同网站分数差异这么大?
查看原帖
为什么不同网站分数差异这么大?
417018
dark_moon楼主2022/10/30 11:32

我有一个朋友(真的有朋友),他在洛谷上AC,但是到别的网站测有90分的,更有甚者50分,但我们都找不出有什么问题(我没认真找),所以想让大佬们帮忙看看有啥问题。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100005],b[100005],n,m,asks,lg2[100005];
struct st{
	int f11[100005][25],f21[100005][25],f12[100005][25],f22[100005][25],p[100005];
	void init(){
		memset(f11,-0x3f,sizeof(f11));
		memset(f21,0x3f,sizeof(f21));
		memset(f12,-0x3f,sizeof(f12));
		memset(f22,0x3f,sizeof(f22));
		for(int i=1;i<=n;i++){if(p[i]==0)f11[i][0]=f12[i][0]=f21[i][0]=f22[i][0]=0;else if(p[i]<0)f11[i][0]=f21[i][0]=p[i];else f12[i][0]=f22[i][0]=p[i];}
		for(int i=1;i<=18;i++){
			for(int j=1;j<=n-(1<<i)+1;j++){
				f11[j][i]=max(f11[j][i-1],f11[j+(1<<i-1)][i-1]);
				f12[j][i]=max(f12[j][i-1],f12[j+(1<<i-1)][i-1]);
				f21[j][i]=min(f21[j][i-1],f21[j+(1<<i-1)][i-1]);
				f22[j][i]=min(f22[j][i-1],f22[j+(1<<i-1)][i-1]);
			}
		}
	}
	int gmin1(int l,int r){
		int k=lg2[r-l+1];
		return min(f21[l][k],f21[r-(1<<k)+1][k]);
	}
	int gmin2(int l,int r){
		int k=lg2[r-l+1];
		return min(f22[l][k],f22[r-(1<<k)+1][k]);
	}
	int gmax1(int l,int r){
		int k=lg2[r-l+1];
		return max(f11[l][k],f11[r-(1<<k)+1][k]);
	}
	int gmax2(int l,int r){
		int k=lg2[r-l+1];
		return max(f12[l][k],f12[r-(1<<k)+1][k]);
	}
	int gmin(int l,int r){
		return min(gmin1(l,r),gmin2(l,r));
	}
	int gmax(int l,int r){
		return max(gmax1(l,r),gmax2(l,r));
	}
}q1,q2;
signed main(){
	freopen("game15.in","r",stdin);
	freopen("game15.out","w",stdout);
	for(int i=1;i<=100000;i++)lg2[i]=log2(i); 
	cin>>n>>m>>asks;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),q1.p[i]=a[i];
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]),q2.p[i]=b[i];
	q1.init();q2.init();
	while(asks--){
		int l1,r1,l2,r2;
		scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
		int am=q1.gmax(l1,r1),an=q1.gmin(l1,r1),bm=q2.gmax(l2,r2),bn=q2.gmin(l2,r2);
		if(bn>=0){
			if(an>=0)printf("%lld\n",q1.gmax(l1,r1)*q2.gmin(l2,r2));
			else if(am<=0)printf("%lld\n",q1.gmax(l1,r1)*q2.gmax(l2,r2));
			else{
				printf("%lld\n",q1.gmax(l1,r1)*q2.gmin(l2,r2));
			}
		}else if(bm>=0&&bn<=0){
			if(an>=0){
				printf("%lld\n",q1.gmin(l1,r1)*q2.gmin(l2,r2));
			}else if(am<=0){
				printf("%lld\n",q1.gmax(l1,r1)*q2.gmax(l2,r2));
			}else{
				printf("%lld\n",max(q1.gmin2(l1,r1)*q2.gmin1(l2,r2),q1.gmax1(l1,r1)*q2.gmax2(l2,r2)));
			}
		}else{
			if(an>=0)printf("%lld\n",q1.gmin(l1,r1)*q2.gmin(l2,r2));
			else printf("%lld\n",q1.gmin(l1,r1)*q2.gmax(l2,r2));
		}
	}
	return 0;
} 
2022/10/30 11:32
加载中...