QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#548038#7520. Monster GeneratorYoralenWA 1ms10104kbC++142.4kb2024-09-05 14:54:092024-09-05 14:54:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-05 14:54:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10104kb
  • [2024-09-05 14:54:09]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N=50005;
struct Line{
	double k,b;
	bool operator ==(Line A)const{
		return k==A.k&&b==A.b;
	}
}st[N],stl[N];
int n,tp;
double It,m,stt[N],inf=1e18;
long long ans;
double Int(Line l1,Line l2){return (l2.b-l1.b)/(l1.k-l2.k);}
struct node{double a,ka,b,kb;}st1[N],st2[N],a[N];
void Ins(Line l){
	while(tp>=2&&Int(l,st[tp-1])<=Int(st[tp-1],st[tp]))tp--;
	if(tp==1&&Int(st[tp],l)<=It)tp--;st[++tp]=l;
}
bool cmp(Line l1,Line l2){return l1.k<l2.k||(l1.k==l2.k&&l1.b>l2.b);}
bool cmp1(node A,node B){return A.a+It*A.ka<B.a+It*B.ka;}
bool cmp2(node A,node B){return A.b+It*A.kb>B.b+It*B.kb;}
signed main(){
	int i,j,tpt=0;
	scanf("%lld%lf",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%lf%lf%lf%lf",&a[i].a,&a[i].ka,&a[i].b,&a[i].kb);
		if(a[i].ka!=a[i].kb){
			double v=(a[i].b-a[i].a)/(a[i].ka-a[i].kb);
			if(v>0&&v<m)stt[++tpt]=v;
		}
	}
	for(i=1;i<n;i++){
		for(j=i+1;j<=n;j++){
			if(a[i].ka!=a[j].ka){
				double v=(a[j].a-a[i].a)/(a[i].ka-a[j].ka);
				if(v>0&&v<m)stt[++tpt]=v;
			}
			if(a[i].kb!=a[j].kb){
				double v=(a[j].b-a[i].b)/(a[i].kb-a[j].kb);
				if(v>0&&v<m)stt[++tpt]=v;
			}
		}
	}
	
	sort(stt+1,stt+1+tpt);
	double l=0,r;int L=0,R;
	for(i=0;i<=tpt;i++){
		if(i<tpt)r=stt[i+1];
		else r=m;R=(int)(r);
		if(L<=R){
		//	printf("!%lf %lf %lld %lld\n",l,r,L,R);
			int tp1=0,tp2=0;
			for(j=1;j<=n;j++){
				if(a[j].b+a[j].kb*L>=a[j].a+a[j].ka*L)st1[++tp1]=a[j];
				else st2[++tp2]=a[j];
			}
			It=L;
			sort(st1+1,st1+1+tp1,cmp1);
			sort(st2+1,st2+1+tp2,cmp2);
			double B=0,K=0;int tpl=0;
			for(j=1;j<=tp1;j++){
				B+=st1[j].a,K+=st1[j].ka;
				stl[++tpl]=(Line){K,B};
				B-=st1[j].b,K-=st1[j].kb;
			}
			for(j=1;j<=tp2;j++){
				B+=st2[j].a,K+=st2[j].ka;
				stl[++tpl]=(Line){K,B};
				B-=st2[j].b,K-=st2[j].kb;
			}
			sort(stl+1,stl+1+tpl,cmp);tp=0;
			for(j=1;j<=tpl;j++){
				if(j==1||stl[j].k!=stl[j-1].k)Ins(stl[j]);
			}
			double lim=L,rim;
			int Cl=L,Cr;
			for(j=1;j<=tp;j++){
				if(j<tp)rim=Int(st[j],st[j+1]);
				else rim=inf;
				Cr=min(R,(int)rim);
			//	printf("@%lf %lf %lld %lld\n",st[j].k,st[j].b,Cl,Cr);
				if(Cl<=Cr){
					ans+=max(0.0,st[j].b*(Cr-Cl+1)+st[j].k*(Cl+Cr)*(Cr-Cl+1)/2);
				}
				Cl=Cr+1;
				lim=rim;if(Cr==R)break;
			}
		}
		l=r;L=R+1;
	//	printf("#%lld\n",ans);
	}
	printf("%lld",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10044kb

input:

3 5
3 1 5 2
4 2 1 3
1 9 100 1

output:

113

result:

ok single line: '113'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 10104kb

input:

3 100000000
3 1 5 2
4 2 1 3
1 9 100 1

output:

35000000549999996

result:

wrong answer 1st lines differ - expected: '35000000549999998', found: '35000000549999996'