马蜂良好,95pts求调玄学问题
查看原帖
马蜂良好,95pts求调玄学问题
561184
fogflea楼主2024/10/20 21:50

写下来感觉没什么问题就交了

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int MAXN=INT_MAX;
const int N=1e5+1;
ll n,m,q,l1,l2,r1,r2,a[N],b[N];
ll Amax,Amin,A1max,A0min,Bmax,Bmin,s1;
ll sta[2][N][25],stb[2][N][25],sta0[2][N][25],Log2[N];
void initST(ll (&st)[2][N][25],ll n){
	for(ll f=0;f<=1;++f)
	for(ll l=1;l<=24;++l)
	for(ll i=1;i+(1<<l)-1<=n;++i)
	st[f][i][l]=min(st[f][i][l-1],st[f][i+(1<<l-1)][l-1]);	
}
void initSTA0(ll n){
	for(ll i=1;i<=n;++i){
		if(a[i]>0)
		sta0[0][i][0]=a[i],sta0[1][i][0]=-MAXN;
		else if(a[i]<0)
		sta0[1][i][0]=a[i],sta0[0][i][0]=MAXN;
	}
	for(ll l=1;l<=24;++l)
	for(ll i=1;i+(1<<l)-1<=n;++i){
		sta0[0][i][l]=min(sta0[0][i][l-1],sta0[0][i+(1<<l-1)][l-1]);
		sta0[1][i][l]=max(sta0[1][i][l-1],sta0[1][i+(1<<l-1)][l-1]);
	}	
}
ll find(ll (&st)[2][N][25],ll f,ll l,ll r){
	ll x=Log2[r-l+1];
	return min(st[f][l][x],st[f][r-(1<<x)+1][x]);
}
ll findsta0(ll f,ll l,ll r){
	ll x=Log2[r-l+1];
	return (f==0)?min(sta0[f][l][x],sta0[f][r-(1<<x)+1][x]):max(sta0[f][l][x],sta0[f][r-(1<<x)+1][x]);
}
void initLog2(ll n){
	for(ll i=2;i<=n;++i)
	Log2[i]=Log2[i>>1]+1;
}
int main(){
//	freopen("P8818_3.in","r",stdin);
//	freopen("game.out","w",stdout);
	
	scanf("%lld%lld%lld",&n,&m,&q);
	for(ll i=1;i<=n;++i)scanf("%lld",&a[i]),sta[0][i][0]=a[i],sta[1][i][0]=-a[i];
	for(ll i=1;i<=m;++i)scanf("%lld",&b[i]),stb[0][i][0]=b[i],stb[1][i][0]=-b[i];
	
	initST(sta,n),initST(stb,m),initSTA0(n);
	initLog2(max(n,m));
	
	while(q--){
		scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
		Amax=-find(sta,1,l1,r1);
		Amin=find(sta,0,l1,r1);
		A1max=findsta0(1,l1,r1);
		A0min=findsta0(0,l1,r1);
		Bmax=-find(stb,1,l2,r2);
		Bmin=find(stb,0,l2,r2);
		
		if(Bmax>0&&Bmin>0){
			if(Amax<0)s1=Amax*Bmax;
			else s1=Amax*Bmin;
		}else if(Bmax<=0&&Bmin<=0){
			if(Amin<0)s1=Amin*Bmax;
			else s1=Amin*Bmin;
		}else{
			s1=max(A0min*Bmin,A1max*Bmax);
		}
		
		
		printf("%lld\n",s1);
	}
	return 0;
}

然而95pts,WA subtask0 #36和subtask1 #3 #9, 然后注意到应该是MAXN的问题。于是改了改。

const ll MAXN=1e18;

40pts...

然后又改成

const ll MAXN=9e9+9e7;

少WA了subtask1 #3 之后尝试了MAXN的多种赋值,如LONG_LONG_MAX,1e17,1e16...

发现以下不严谨规律

pts={95,MAXN<9e9+9e840,MAXN9e9+9e8MAXN1e1745,MAXN=1e17pts=\left\{ \begin{aligned} &95,MAXN<9e9+9e8 \\ &40,MAXN\geq9e9+9e8且MAXN\neq1e17\\ &45,MAXN=1e17 \end{aligned} \right.

今晚在机房三个小时都在调这个玄学问题,已红,望有佬相助,多谢。

2024/10/20 21:50
加载中...