蒟蒻求助 为什么会MLE
查看原帖
蒟蒻求助 为什么会MLE
38171
DeNeRATe楼主2020/4/27 10:19
//P4774
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define INF 0x7fffffff
using namespace std;
const int MAXn=1e5+10;

LL A[MAXn],M[MAXn],X,Y,Least,Test,Reward[MAXn];
LL XX[MAXn];
LL Hp[MAXn],Up[MAXn],Total,Sward,Root;
LL Child[MAXn][2],Weight[MAXn],Val[MAXn],Size[MAXn],Cnt;
bool Jud,Flag;

inline void Update(LL New) { Size[New]=1+Size[Child[New][1]]+Size[Child[New][0]]; }
inline LL New_Node(LL Temp) {
	Size[++Cnt]=1;
	Weight[Cnt]=rand();
	Val[Cnt]=Temp;
	return Cnt;
}

inline void Split(LL New,LL Limit,LL &L,LL &R) {
	if(!New) L=R=0;
	else {
		if(Val[New]<=Limit) { L=New; Split(Child[New][1],Limit,Child[New][1],R); }
		else { R=New; Split(Child[New][0],Limit,L,Child[New][0]); }
		Update(New);
	}	
}

inline LL Merge(LL L,LL R) {
	if(!L || !R) return L+R;
	if(Weight[L]<Weight[R]) { Child[L][1]=Merge(Child[L][1],R); Update(L); return L; }
	else { Child[R][0]=Merge(L,Child[R][0]); Update(R); return R; }
}

inline void Insert(LL Temp) {
	LL R1,R2,R3;
	Split(Root,Temp,R1,R2);
	Root=Merge(Merge(R1,New_Node(Temp)),R2);
}

inline void Delete(LL New) {
	LL R1,R2,R3;
	Split(Root,Val[New]-1,R1,R2);
	Split(R2,Val[New],R2,R3);
	Root=Merge(R1,R3);
}

inline LL Front(LL New) {
	while(Child[New][1]) New=Child[New][1];
	return New;
}

inline LL Back(LL New) {
	while(Child[New][0]) New=Child[New][0];
	return New;
}

inline LL Ex_GCD(LL L,LL R) {
	if(!R) { X=1; Y=0; return L; }
	LL Res=Ex_GCD(R,L%R);
	LL Temp=X; X=Y; Y=Temp-(L/R)*Y;
	return Res;
}

inline void MLE(LL L,LL R,LL N,LL ID) {
	X=Y=0;
	LL Res=Ex_GCD(L,R);
	if(N%Res) { Jud=false; return; }
	LL Temp=R/Res,X0=X*(N/Res);
	A[ID]=(X0%Temp+Temp)%Temp; M[ID]=Temp;
}

inline void Ex_CRT() {
	LL A1=A[1],M1=M[1];
	FOR(i,2,Total) {
		X=Y=0;
		LL A2=A[i],M2=M[i];
		LL Res=Ex_GCD(M1,M2),C=A2-A1;
		if(C%Res) { cout<<"-1"<<endl; return; }
		LL Temp=M2/Res;
		LL X0=(X*(C/Res)%Temp+Temp)%Temp;
		LL MOD=M1*M2/Res;
		A1=((X0*M1+A1)%MOD+MOD)%MOD;
		M1=MOD;
	}
	printf("%lld\n",A1%M1);
}

inline void Clean() {
	Root=0; Cnt=0; Cl(Child,0);
	Least=0; Jud=true; Flag=true;
}

inline void Work() {
	LL Ans=0;
	FOR(i,1,Total) Ans=max(Ans,(Hp[i]-1)/XX[i]+1);
	printf("%lld\n",Ans);
}

int main() {
	scanf("%lld",&Test);
	while(Test--) {
		Clean();
		scanf("%lld %lld",&Total,&Sward);
		FOR(i,1,Total) scanf("%lld",&Hp[i]);
		FOR(i,1,Total) scanf("%lld",&Up[i]);
		FOR(i,1,Total) scanf("%lld",&Reward[i]);
//		cout<<"true"<<endl;
		FOR(i,1,Sward) { LL Temp; scanf("%lld",&Temp); Insert(Temp); }
//		cout<<"true"<<endl;
		FOR(i,1,Total) {
			LL R1,R2,Temp;
//			cout<<"true"<<endl;
			Split(Root,Hp[i],R1,R2);
//			cout<<"true"<<endl;
			if(Size[R1]) Temp=Front(R1);
			else Temp=Back(R2);
//			cout<<"true"<<endl;
			XX[i]=Val[Temp];
			Root=Merge(R1,R2);
//			cout<<"true"<<endl;
			Delete(Temp);
			Insert(Reward[i]);
		}
		FOR(i,1,Total) 	if(Up[i]!=1) Flag=false;
		if(Flag) { Work(); continue; }
		FOR(i,1,Total) {
			MLE(XX[i],Up[i],Hp[i],i);
//			cout<<"true"<<endl;
			if(!Jud) { cout<<"-1"<<endl; break; }
		}
		if(!Jud) continue;
		else Ex_CRT();		
	}
	return 0;
}
2020/4/27 10:19
加载中...