QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548080#7520. Monster GeneratorYoralenWA 2ms14012kbC++142.5kb2024-09-05 15:17:202024-09-05 15:17:20

Judging History

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

  • [2024-09-05 15:17:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14012kb
  • [2024-09-05 15:17:20]
  • 提交

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+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);//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;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+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;
			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){
					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+v3*v4*v2/2;
				}
				lim=rim;Cl=Cr+1;
				if(Cr==R)break;
			}
		}
		l=r;L=R+1;
	}
	cout<<ans;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 12028kb

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: 0
Accepted
time: 0ms
memory: 12028kb

input:

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

output:

35000000549999998

result:

ok single line: '35000000549999998'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 14012kb

input:

10 1000000000000000000
776874380544333 197 471391764744275 33
159838820333814 107 677112662750393 41
962335658276824 48 255593531071176 11
127404116579775 209 268525254990127 34
647620110614714 76 897947476313307 13
146196843402516 221 772928712898807 39
637929916804442 2 716937021892338 15
64200226...

output:

8659945148502275542

result:

wrong answer 1st lines differ - expected: '17883317185357051350', found: '8659945148502275542'