QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548153#7520. Monster GeneratorYoralenCompile Error//C++142.5kb2024-09-05 16:02:422024-09-05 16:02:49

Judging History

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

  • [2024-09-05 16:02:49]
  • 评测
  • [2024-09-05 16:02:42]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
typedef unsigned long long ull;
const int N=100005;
struct Line{
	long double k,b;
	bool operator ==(Line A)const{
		return k==A.k&&b==A.b;
	}
}st[N],stl[N];
int n,tp;
long double It,m,stt[N],inf=1e18;

ull ans;
long double Int(Line l1,Line l2){return (l2.b-l1.b)/(l1.k-l2.k);}
struct node{long 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-B.a)/It<B.ka-A.ka;}
bool cmp2(node A,node B){return (A.b-B.b)/It>B.kb-A.kb;}
signed main(){
	int i,j,tpt=0;
	scanf("%lld%Lf",&n,&m);//cout<<inf<<'\n';
	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){
			long 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){
				long 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){
				long 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);
	long double l=0,r,L=0,R;
	for(i=0;i<=tpt;i++){
		if(i<tpt)r=stt[i+1];
		else r=m;R=floor(r);
	//	printf("~%.6Lf %.6Lf %.6Lf %.6Lf\n",l,r,L,R);
		if(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+r)/2.0;
			sort(st1+1,st1+1+tp1,cmp1);
			sort(st2+1,st2+1+tp2,cmp2);
			long 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]);
			}
			long double lim=L,rim,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,floor(rim));
				if(Cl<=Cr){
					//cout<<'^'<<Cl<<' '<<Cr<<'\n';
					ull v1=(ull)(st[j].b),v2=(ull)(Cr-Cl+1);
					ull v3=(ull)(st[j].k),v4=(ull)(Cl+Cr);
					ans=ans+v1*v2;
					if(v2&1)v4>>=1;
					else v2>>=1;
					ans=ans+(v3*v4)*v2;
				}
				lim=rim;Cl=Cr+1;
				if(Cr==R)break;
			}
		}
		l=r;L=R+1;
	}
	cout<<ans;
}

詳細信息

answer.code: In function ‘int main()’:
answer.code:53:28: error: ‘floor’ was not declared in this scope
   53 |                 else r=m;R=floor(r);
      |                            ^~~~~
answer.code:29:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   29 |         scanf("%lld%Lf",&n,&m);//cout<<inf<<'\n';
      |         ~~~~~^~~~~~~~~~~~~~~~~
answer.code:31:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |                 scanf("%Lf%Lf%Lf%Lf",&a[i].a,&a[i].ka,&a[i].b,&a[i].kb);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~