QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#548038 | #7520. Monster Generator | Yoralen | WA | 1ms | 10104kb | C++14 | 2.4kb | 2024-09-05 14:54:09 | 2024-09-05 14:54:11 |
Judging History
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'